tyvj 1233 数列删除数列一些数后使得a[i]=i的数最多

本文链接：https://blog.csdn.net/kongming_acm/article/details/6039103

这是一个关于利用动态规划算法解决数列问题的程序。给定一个整数数列，目标是删除一些数，使得剩余的数满足a[i]=i的情况最多。程序通过二维数组dp记录删除不同数量的数后的最大满足条件的数，并最终输出最大值。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

	虽然msh长大了，但她还是很喜欢找点游戏自娱自乐。有一天，她在纸上写了一串数字：1,1,2,5,4。接着她擦掉了一个1，结果发现剩下1,2,4都在自己所在的位置上，即1在第1位，2在第2位，4在第4位。她希望擦掉某些数后，剩下的数列中在自己位置上的数尽量多。她发现这个游戏很好玩，于是开始乐此不疲地玩起来……不过她不能确定最多能有多少个数在自己的位置上，所以找到你，请你帮忙计算一下！


	输入格式 Input Format
		第一行为一个数n，表示数列的长度。接下来n个数，每次一个正整数，第i个表示数Ai。


	输出格式 Output Format
		一行一个整数，表示擦掉某些数后，最后剩下的数列中最多能有多少个数在自己的位置上，即Ai=i最多能有多少。


	样例输入 Sample Input
		5 1 1 2 5 4


	样例输出 Sample Output
		3


	时间限制 Time Limitation
		各个测试点1s


	注释 Hint
		对于20%的数据，n<=20; 对于60%的数据，n<=100; 对于100%的数据，n<=1000.

Flag	Accepted
题号	P1233
类型(?)	动态规划
通过	263人
提交	528次
通过率	50%
难度	0

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[1100];
int dp[1100][1100];//dp[i][j]表示前i个数删除j个数后的最大值
/* dp[i][j]=max{
dp[i-1][j]+1;//i在自己的位置上，即a[i]=i-j
dp[i-1][j-1];//i不在自己的位置上，删掉
dp[i-1][j];//i不在自己的位置上，占位置
}*/
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                if(a[i]==i-j) dp[i][j]=dp[i-1][j]+1;
                else dp[i][j]=dp[i-1][j-1];
                if(dp[i-1][j]>dp[i][j]) dp[i][j]=dp[i-1][j];
            }
        }
        int _max=0;
        for(int i=0;i<=n;i++) if(dp[n][i]>_max) _max=dp[n][i];
        printf("%d/n",_max);
    }
    return 0;
}