【题目描述】 让计算机这样读入一列非负整数： 1、读入数T。 2、接着往下读入T个数。 3、如果数列读完了，则停止，否则，转到1。 但是，往往会出现这样的问题：执行第2步时，数列已经没有T个数了。如果这样，我们称这个数列是“不可接受的”，否则，称它是“可接受的”。我们需要用最少的步数把一个数列变成“可接受的”，一步是指： 1、把数列中的某一个数加1。 2、把数列中的某一个数减1。 【输入格式】 第一行有一个数N (1<=N<=1000000)，表示数列的长度，接下来有n行，描述这个数列，每一行有一个非负整数（不超过1000000）。 【输出格式】 仅一个数，表示最少的步数。 【输入输出样例】 sequence.in sequence.out 7 3 1 2 3 4 5 6 1 【数据规模】 对于50%的数据，N≤1,000； 对于80%的数据，N≤100,000； 对于100%的数据，N≤1,000,000。
//DP f[i]表示走到第i个数字的最小操作数 #include<iostream> #include<cstdio> #include<cstring> using namespace std; #define MAXN 1000010 int f[MAXN],s[MAXN],n; inline void read(int &x){ x=0; int f=1; char c=getchar(); while(c>'9'||c<'0'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9'){ x=x*10+c-'0'; c=getchar(); } x*=f; } int main(){ read(n); for(int i=1;i<=n;++i) read(s[i]),f[i]=MAXN; f[1]=0,f[n+1]=MAXN; for(int a,b,c,i=1;i<=n;++i){ a=i+s[i]+1,b=f[i]; if(a>n+1){ c=a-n; for(int j=n+1;j>i&&f[j]>n-j+b+c;--j) f[j]=n-j+b+c; } else if(f[a]>b){ f[a]=b; for(int j=a-1;j>i&&f[j]>a-j+b;--j) f[j]=a-j+b; for(int j=a+1;j<=n+1&&f[j]>j-a+b;++j) f[j]=j-a+b; } } printf("%d\n",f[n+1]); return 0; }