[数据结构与算法]洛谷1799——数列

题目描述
虽然 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

思路：
d[i][j]表示1到i中删除j个数满足条件的最大个数，d[i][j]的前一种情况可能是d[i-1][j-1]和d[i-1][j]，若第i个数删除，则为d[i][j]=d[i-1][j-1]，若第i个数不删，则d[i][j]=d[i-1][j]，考虑当a[i]==i-j时，若第i个数不删，则符合位置条件的数增加一个，所以比较d[i-1][j-1]和d[i-1][j]+1。

// 1799
#include <bits/stdc++.h>
using namespace std;
int d[1010][1010]; //全局变量，默认为0，避免数组过大崩溃 
//d[i][j]表示1到i中删除j个数满足条件的最大个数 
int main()
{
	int i,j,n,a[1010]; 
	int f=0; //初始化标记为0
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i];
	for(i=1;i<=n;i++) //初始化 
    {
        d[i][0]=d[i-1][0]; //未删除 
        if(a[i]==i) //统计初始时满足条件个数 
        	d[i][0]++;
    }
	for(i=1;i<=n;i++)
	{
		for(j=0;j<=i;j++)
		{
  			if(a[i]==i-j) //删除数之后的位置满足条件 
            {
                d[i][j]=max(d[i-1][j-1],d[i-1][j]+1);
            }
            else //前i个数删除j个，考虑第i个数删和不删的情况 
				d[i][j]=max(d[i-1][j-1],d[i-1][j]);
		}
	}
	for(int i=0;i<=n;i++)
    	f=max(f,d[n][i]); //找出最大值 
	cout<<f;	
	return 0;
}