2020牛客NOIP赛前训练营-普及组第一场牛牛的跳跳棋题解

链接：https://ac.nowcoder.com/acm/contest/7604/B
来源：牛客网

题目描述

牛牛最近在玩一种叫做跳跳棋的游戏，棋盘可以看成是一个一维的线性数组，编号从1到n+1。

一开始牛牛的棋子位于第1个格子，游戏的最终目的是将棋子移动到第n+1个格子。

棋盘1~n的每个格子都有一个“弹力系数”的权值pi。

当棋子位于第i个格子时，它的下一步可以移动到[i−pi,i+pi]范围内的任意一个格子。

举例来说，假设第3个格子的弹力系数为2，那么牛牛下一步可以移动到第1,2,3,4,5格中的任意一格。

现在给定1~n每格的弹力系数pi。

 

牛牛发现，好像有时由于棋盘的pi设置不合理，导致游戏无法通关。

所以牛牛准备施展他神奇的魔法，他每次施展魔法都可以使得一个格子的弹力系数pip_ipi+1，他可以施展若干次魔法操作不同的格子，但是要求他不能够重复对一个格子施展魔法。

牛牛想要知道，为了使跳跳棋通关，他最少施展多少次魔法，并且他应该操作哪些格子。

请输出牛牛的最小操作次数，以及施展魔法的操作序列，操作序列的第i个数表示该次施展魔法的格子编号，由于答案不唯一，所以请你输出一个最小字典序的答案。

 

最小字典序指：在保证第1个数字尽可能小的前提下，保证第2个数字尽可能的小，然后在此前提下保证第3个数字尽可能的小....以此类推。

输入描述:

1 2 3 4 5 6 7

第一行输入一个正整数n表示跳跳棋的格子数目。       接下来输入一行n个非负整数pi表示跳跳棋前n个格子的弹力系数。

输出描述:

1 2 3 4 5 6 7

首先输出一个非负整数ans，表示少施展魔法的次数。       如果ans不为0，则再输出一行ans个整数表示需要施展魔法的格子编号，请给出一个最小字典序的答案。

示例1

输入

1 2	12 5 4 3 3 2 1 0 0 0 1 0 0

输出

1 2	5 4 8 9 10 12

思路

本来以为是dp，考虑到棋子往回走到某个点可以跳得更远，后来想了一下，棋子可以在【i-pi，i+pi】范围内任意移动，说明如果后面有可以跳得更远得地方，我可以一开始就直接跳到更远得地方，根本没必要回退。

直接用s表示不用魔法所能到达得最远距离，当i>s时说明游戏无法通关，*使用魔法。

AC代码

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include<bits/stdc++.h> using namespace std; int a[100005]; int main() {     int cn=0,s=1,b=1,x,n;//s表示不用魔法能到达的最远距离     scanf("%d",&n);     //b记录能到达最远距离的最小下标     for(int i=1;i<=n;++i)//保证字典序最小     {         scanf("%d",&x);         if(i>s)           a[cn++]=b;//没办法，*使用魔法         if(i+x>s)           s=i+x,b=i;//最远距离更新，顺便记录最小下标     }     if(s!=n+1)       a[cn++]=b;     printf("%d\n",cn);     for(int i=0;i<cn;++i)       printf("%d%c",a[i],i==cn-1?'\n':' ');     return 0; }

本文地址：https://blog.csdn.net/weixin_45615224/article/details/109273251