A40959. 删除数字
填空题
较难
知识点
题目描述
删除数字
题目描述
娇娇一年级了，刚学会了识数和比大小。 昨天，她在黑板上写上一串数字：2，1，2，5，4。接着她擦掉了第一个2，发现剩下的1，2，4都在自己的位置上，即：1在第1位，2在第2位，4在第4位。
娇娇希望在自己的上擦掉一些数后能有几个问题，她的数数在自己上的位置上。 ！
输入
第一行，有一个TestNum(每10个)，表示每行的数据组数。 1000)。
输出
每组测试数据，输出一个数字表示答案。
样例输入
3
5
2 1 2 5 4
7
2 2 3 2 4 5 3
10
1 1 2 2 3 3 4 4 5 5样例输出
3
4
5提示
第一组测试数据：擦掉第一个数，1 2 4 有 3 个数在自己的位置上。
第二组测试数据：擦掉第4个、第7个数，2 3 4 5 有 4 个数在自己的位置上。
第三组测试数据：每种相同的数擦掉一个，1 2 3 4 5 有 5 个数在自己的位置上。
参考答案
#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;
}
上一题
下一题