题目描述
虽然msh长大了，但她还是很喜欢找点游戏自娱自乐。有一天，她在纸上写了一串数字：1，1，2，5，4。接着她擦掉了一个l，结果发现剩下1，2，4都在自己所在的位置上，即1在第1位，2在第2位，4在第4位。她希望擦掉某些数后，剩下的数列中在自己位置上的数尽量多。她发现这个游戏很好玩，于是开始乐此不疲地玩起来……不过她不能确定最多能有多少个数在自己的位置上，所以找到你，请你帮忙计算一下！
输入输出格式
输入格式：
第一行为一个数n，表示数列的长度。
接下来一行为n个用空格隔开的正整数，第i行表示数Ai。
输出格式：
一行一个整数，表示擦掉某些数后，最后剩下的数列中最多能有多少个数在自己的位置上，即Ai=i最多能有多少。
输入输出样例
输入样例#1：
5
1 1 2 5 4
输出样例#1：
3
说明
对于20%的数据，n≤20;
对于60%的数据，n≤100;
对于100%的数据，n≤1000。
题解
先吐嘈一下luogu这个字粘过来真是丑
这道题dp就星了。
设f[i][j]为前i个中留j个 最多有多少个对上。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define R register
inline int read()//以为要卡常于是写的read
{
char ch=getchar();
int x=0;bool s=1;
while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return s?x:-x;
}
int f[5007][5007];
int main()
{
//freopen("game.in","r",stdin);
//freopen("game.out","w",stdout);
int n=read();
for(R int i=1;i<=n;++i)
{
int x=read();
for(R int j=1;j<=i;++j)
f[i][j]=max(f[i-1][j-1],f[i-1][j]);//把这个留住 和不留住中间选更优的
if(x<=i)f[i][x]=max(f[i][x],f[i-1][x-1]+1);//当前留住的正好对位 则++
}
int ans=0;
for(R int j=n;j>=0;--j)
ans=max(ans,f[n][j]);//统计答案
cout<<ans;
return 0;
}