牛牛的跳跳棋题解

牛牛的跳跳棋

https://ac.nowcoder.com/acm/contest/7604/B

链接：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个数字尽可能的小....以此类推。

输入描述:

	
		第一行输入一个正整数n表示跳跳棋的格子数目。
	

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

输出描述:

	
		首先输出一个非负整数ans，表示少施展魔法的次数。
	

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

示例1

输入

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

输出

5
4 8 9 10 12

思路

本来以为是dp，考虑到棋子往回走到某个点可以跳得更远，后来想了一下，棋子可以在【i-pi，i+pi】范围内任意移动，

说明如果后面有可以跳得更远得地方，我可以一开始就直接跳到更远得地方，根本没必要回退。

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

AC代码

#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;
}