题目链接： 传送门
思路：
显然，这是一个DAG，而且1 2 3 ... n-1 n 是该图的一个拓扑序。
定义f(i,j)表示 唯一能到达 i 的路径, 满足 a[k] + k <= j , k∈[1,i) , 换言之 i 表示之前的点能覆盖到的标号最大的点 <= j .
f(i,j+aj) <-- f(j,i-1) + cntj , cntj 表示需要置零的点的数目，j∈[1,i-1) ， 由于 f(j,i-1) 的定义，那么[1,j）中所有能到达i 的点已经被删掉了，那么 还需要处理 (j, i) 的点，因此cntj = ∑i-1k=j+1 ( a[k] + k >= i)
该状态及转移方程能表示每种路径的唯一性，能避免转移时 既要考虑前面的点 又要考虑后面的点的后效性。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 typedef unsigned long long uLL; 5 typedef pair<int,int> pii; 6 typedef pair<LL,LL> pLL; 7 typedef pair<double,double> pdd; 8 const int N=3e3+5; 9 const int M=1e7+5; 10 const int inf=0x3f3f3f3f; 11 const LL mod=998244353; 12 const double eps=1e-8; 13 const long double pi=acos(-1.0L); 14 #define ls (i<<1) 15 #define rs (i<<1|1) 16 #define fi first 17 #define se second 18 #define pb push_back 19 #define eb emplace_back 20 #define mk make_pair 21 #define mem(a,b) memset(a,b,sizeof(a)) 22 LL read() 23 { 24 LL x=0,t=1; 25 char ch; 26 while(!isdigit(ch=getchar())) if(ch=='-') t=-1; 27 while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); } 28 return x*t; 29 } 30 int a[N],f[N][N]; 31 int main() 32 { 33 int T=read(); 34 while(T--) 35 { 36 int n=read(); 37 for(int i=1;i<=n;i++) a[i]=read(); 38 for(int i=2;i<=n;i++) 39 for(int j=1;j<=n;j++) 40 f[i][j]=inf; 41 for(int i=1;i<=n;i++) f[1][i]=0; 42 for(int i=2;i<=n;i++) 43 { 44 int cnt=0; 45 for(int j=i-1;j;j--) 46 { 47 if(j+a[j]<i) continue; 48 f[i][j+a[j]]=min(f[i][j+a[j]],f[j][i-1]+cnt); 49 cnt++; 50 } 51 for(int j=2;j<=n;j++) 52 f[i][j]=min(f[i][j],f[i][j-1]); 53 } 54 printf("%d ",f[n][n]); 55 } 56 return 0; 57 }