7 E. Block Sequence

链接

E. Block Sequence

题意

一个数组删除最少的数使数组变为美丽的
美丽的定义：
第一个数是长度看，后面k是k个数。

题解

考虑dp
$f[i]$表示将从i到n的所有数都变成美丽的花费最小
转移
$f[i]=min(f[i+1]+1,f[i+a[i]+1]);$
初始化：
$f[n]=1;$
$f[n+1]=0$:这里表示一个都不删从第一个到第n个恰好是美丽的
这个是从后往前推，所以是倒序循环。
答案就是$f[1]$

代码

#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_backusing namespace std;void solve() {int n;cin>>n;vector<int>a(n+2);rep(i,1,n){cin>>a[i];}vector<int>f(n+2);f[n]=1;f[n+1]=0;fep(i,n-1,1){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() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("1.in", "r", stdin);int _;cin>>_;while(_--)solve();return 0;
}

总结

非常不错的一道dp题目。
给自己的启发是dp的顺序不止能从前往后，也可以逆序，只要初始化好状态。