题面
有一行 (n) 个鸽子，每个鸽子有个跳跃能力 (a_i)，表示站在这个鸽子上的人可以跳到每个满足 (i+1le j< i+a_i) 的第 (j) 个鸽子。现在有个人在第 (1) 只鸽子身上，他的目标是跳到第 (n) 子鸽子身上。请问您最少杀死几只鸽子（使 (a_i) 变成 (0)），使得这个人到最后一个鸽子有正好 (1) 种方案。
数据范围：(2le nle 3000)，(0le a_ile n-i)。
题解
什么时候 Codeforces 有这么 AtCoder 的题了 /yiw。
为了方便，令 (a_i=a_i+1)（题面中条件是已经加过了的）。
有一种基于暴力的 naive 做法，可是是错的：
设 (f_{i,k}) 表示到第 (i) 个鸽子，有 (k) 种方案的最小宰鸽数（如果有 (>2) 种方案当作 (2)）。
可是数据 1
5
3 1 2 1 0
把我宰了，因为这种做法会重复统计宰鸽。
考虑分析这个唯一的被人踩了的鸽子的序列 (p_1,p_2,dots ,p_m)，会发现以下性质：
-
对于每个 (p_i)，这只鸽子肯定没有被宰掉，且 (p_i+a_{pi}>p_{i+1})。
-
每个 (p_i) 必须满足 (p_i+a_{pi}le p_{i+2})。否则如下图最下面的红边，就会多产生一种方案。
-
每个 (p_i<j<p_{i+1}) 必须满足 (j+a_jle p_{i+1})。否则 (p_i) 先走橙色边，再走短的红边，就会多产生一种方案。
所以可以尝试维护 (f[u][v]) 表示最后两个 (p_i) 是 (u,v) 的方案数，然后就有了一个 (Theta(n^3)) 的做法。
然后可以发现，如果给 (u)（从左往右第 (2) 个黄鸽）向右延伸的边（绿边）一个右滑的机会，那么转移可以变成 (Theta(n^2))。
即设 (f[v][j]) 表示当前最后一个 (p_i=v)，然后 (p_{i-1}) 可以跳到 (j) 之前的最小宰鸽数。
(v) 即是图中间的黄鸽子，(j) 即所有绿鸽子。转移的下一个 (v') 即最右端的肉鸽子。
转移过程就是枚举 (v') 和 (v)，然后从 (f[v][v']) 转移到 (f[v'][v+a_v])，代价是把 (v) 和 (v') 之间可以跳到 (v') 右边的鸽子全部宰掉。
然后把第二维前缀最小值一下，表示一个滑的过程。
代码
//George1123
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define x first
#define y second
#define sz(a) (int)((a).size())
#define all(a) (a).begin(),(a).end()
#define R(i,n) for(int i=0;i<(n);++i)
#define L(i,n) for(int i=(n)-1;i>=0;--i)
constexpr int inf32=0x3f3f3f3f;
constexpr i64 inf64=0x3f3f3f3f3f3f3f3f;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t;
for(cin>>t;t--;){
int n;
cin>>n;
vi a(n);
R(i,n) cin>>a[i],++a[i];
vector<vi> f(n,vi(n+1,inf32));
R(i,n)if(i) f[0][i]=0;
R(i,n)if(i){
int c=0;
L(j,i){
if(j+a[j]<=i) continue;
f[i][j+a[j]]=min(f[i][j+a[j]],f[j][i]+(c++));
}
for(int j=i+1;j<n;++j)
f[i][j+1]=min(f[i][j+1],f[i][j]);
}
cout<<f[n-1][n]<<'
';
}
return 0;
}
/*
1
5
3 1 2 1 0
*/
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
祝大家能踩着我这只被杀死的鸽子，越飞越远！