简答题 偏难
#7061

删除数字 娇娇一年级了,刚刚学会了识数和比大小。有一天,她在黑板上写上了一串数字: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 个数在自己的位置上。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; using namespace std; struct node {   int data, lenth;   int next; } a[1010]; int main() {   int t, n, i, j, p, maxn, o;   cin &gt;&gt; t;   for (o = 1; o &lt;= t; o++) {     cin &gt;&gt; n;     for (i = 1; i &lt;= n; i++)       cin &gt;&gt; a[i].data;     a[n].lenth = 1;     a[n].next = 0;     for (i = n - 1; i &gt;= 1; i--) {       maxn = p = 0;       for (j = i + 1; j &lt;= n; j++)         if ((a[j].lenth &gt; maxn) &amp;&amp; (a[i].data &lt; a[j].data)) {           p = j;           maxn = a[j].lenth;         }       a[i].lenth = maxn + 1;       a[i].next = p;     }     maxn = j = 0;     for (i = 1; i &lt;= n; i++)       if (a[i].lenth &gt; maxn) {         maxn = a[i].lenth;         j = i;       }     cout &lt;&lt; maxn &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。