Codeforces Round 903 (Div. 3) E. Block Sequence
题解：
想到从后向前DP
f[i] 表示从 i ~ n 转化为“美观”所需要的最少的步骤
- 第一种转移方式：直接删除掉第i个元素，那么就是上一步 f[i + 1] 加上 1;
- 第二种转移方式：从第 i + a[i] + 1 个元素直接转移，不需要增加步数；
注意边界问题以及初始化，f[n + 1] = 0;
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug(x) cerr << #x" = " << x << '\n';
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int n;
void solve()
{
cin >> n;
vector<int> a(n + 1), f(n + 2);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
f[n + 1] = 0;
for (int i = n; i >= 1; i--) {
f[i] = f[i + 1] + 1;
if(i + a[i] <= n) {
f[i] = min(f[i], f[i + a[i] + 1]);
}
}
cout << f[1] << endl;
}
signed main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int T = 1;
cin >> T;
while (T --) solve();
return 0;
}