简答题
偏难
#7255
删除数字 娇娇一年级了,刚刚学会了识数和比大小。有一天,她在黑板上写上了一串数字:2,1,2,5,4。接着她擦掉了第一个2,发现剩下1,2,4都在自己的位置上,…
删除数字
娇娇一年级了,刚刚学会了识数和比大小。有一天,她在黑板上写上了一串数字:2,1,2,5,4。接着她擦掉了第一个2,发现剩下1,2,4都在自己的位置上,即:1在第1位,2在第2位,4在第4位。
娇娇希望擦掉某些数后,剩下的数列中在自己位置上的数尽量多。她发现这个问题很有趣,想知道最多能有几个数在自己的位置上,请你帮帮她!
时间限制:1000
内存限制:65536
输入
第一行,一个整数 TestNum( ≤ 10),表示测试数据的组数。 接下来每组数据有两行,第一行:一个整数n( ≤ 1000),第二行:n个正整数(≤ 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 个数在自己的位置上。
答案与解析
正确答案:<p>
#include <bits/stdc++.h>
</p>
<p>
using namespace std;
</p>
<p>
int d[1010][1010]; //全局变量,默认为0,避免数组过大崩溃
</p>
<p>
//d[i][j]表示1到i中删除j个数满足条件的最大个数
</p>
<p>
int main()
</p>
<p>
{
</p>
<p>
<span> </span>int i,j,n,a[1010];
</p>
<p>
<span> </span>int f=0; //初始化标记为0
</p>
<p>
<span> </span>cin>>n;
</p>
<p>
<span> </span>for(i=1;i<=n;i++){
</p>
<p>
<span> </span>cin>>a[i];
</p>
<p>
<span> </span>}
</p>
<p>
<span> </span>for(i=1;i<=n;i++){
</p>
<p>
d[i][0]=d[i-1][0]; //未删除
</p>
<p>
if(a[i]==i){ //统计初始时满足条件个数
</p>
<p>
<span> </span>d[i][0]++;
</p>
<p>
}
</p>
<p>
}
</p>
<p>
<span> </span>for(i=1;i<=n;i++){
</p>
<p>
<span> </span>for(j=0;j<=i;j++){
</p>
<p>
<span> </span>if(a[i]==i-j){ //删除数之后的位置满足条件
</p>
<p>
d[i][j]=max(d[i-1][j-1],d[i-1][j]+1);
</p>
<p>
}
</p>
<p>
else{ //前i个数删除j个,考虑第i个数删和不删的情况
</p>
<p>
<span> </span>d[i][j]=max(d[i-1][j-1],d[i-1][j]);
</p>
<p>
<span> </span>}
</p>
<p>
<span> </span>}
</p>
<p>
<span> </span>}
</p>
<p>
<span> </span>for(int i=0;i<=n;i++){
</p>
<p>
<span> </span>f=max(f,d[n][i]); //找出最大值
</p>
<p>
}
</p>
<p>
<span> </span>cout<<f;<span> </span>
</p>
<p>
<span> </span>return 0;
</p>
<p>
}
</p>
<p>
<a href="http://oj.scratchor.com/problem/CD202209_4_4
" target="_blank">>>试试在线提交?季卡以上会员请联系客服,<span><strong>免费</strong></span>开通OJ账号</a>
</p>
解析
解题思路
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。