题目描述
虽然 msh 长大了，但她还是很喜欢找点游戏自娱自乐。有一天，她在纸上写了一串数字：1,1,2,5,4。接着她擦掉了一个 1，结果发现剩下 1,2,4都在自己所在的位置上，即 1 在第 1 位，2 在第 2 位，4 在第 4 位。她希望擦掉某些数后，剩下的数列中在自己位置上的数尽量多。她发现这个游戏很好玩，于是开始乐此不疲地玩起来……不过她不能确定最多能有多少个数在自己的位置上，所以找到你，请你帮忙计算一下！
输入格式
第一行为一个数 n，表示数列的长度。
接下来一行为 n个用空格隔开的正整数，第 i 行表示数 Ai。
输出格式
一行一个整数，表示擦掉某些数后，最后剩下的数列中最多能有多少个数在自己的位置上，即 Ai=i最多能有多少。
输入输出样例
输入：
5
1 1 2 5 4
输出：
3
dpi?j? 表示前 i 个数中删去 j个数后，原来处于前 i 个数当中的数所能满足 ai=i的 i的个数的最大值。
考虑第j个数删除不删除
不删的话，一共删除 j?1个数，可以从 dp[i?1][j?1]转移过来
删除的话，一共删除j个数，可以从 dp[i?1][j]转移过来，如果a[i]＝i-j，说明dp[i][j]=dp[i-1][j]+1；
#include<bits/stdc++.h>
using namespace std;
int dp[1010][1010],a[1010];
int main()
{
int n;
cin >> n ;
for(int i=1;i<=n;i++)
{
cin >> a[i] ;
}
int ans=0;
for (int i=1;i<=n;i++){
for (int j=0;j<=i;j++){
if (j>0) dp[i][j]=dp[i-1][j-1];
dp[i][j]=max(dp[i][j],dp[i-1][j]+(a[i]==i-j));
ans=max(ans,dp[i][j]);
}
}
cout << ans << endl;
return 0;
}
