洛谷 P1799 数列

题目传送门

(f_{i,j}表示到了第i位,已经擦掉了j位的最佳答案)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int n,c[1001],f[1005][1005],len,a[1001],b[1001],ans;

int main() {
	scanf("%d",&n);
	for(int i = 1;i <= n; i++)
		scanf("%d",&a[i]);
	if(a[1] == 1) f[1][0] = 1;
	for(int i = 2;i <= n; i++) {
		for(int j = 1;j <= i; j++)
			f[i][j] = max(f[i-1][j],f[i-1][j-1]);
		if(i == a[i])
			f[i][0] = f[i-1][0] + 1;
		else 
			f[i][0] = f[i-1][0];
		if(i > a[i]) f[i][i-a[i]] = f[i-1][i-a[i]] + 1;
	}
	for(int i = 0;i <= n; i++)
		ans = max(ans,f[n][i]);
	printf("%d",ans);
	return 0;
}