当前位置:首页 > 动态规划 > 01背包 > 正文
洛谷P1799数列[NOI导刊]
146+

题目大意:n个数排成一行,可以从中删除若干个,请问最终剩下的数字,值跟位置能对应上的最多有多少对?

题目描述

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

输入输出格式

输入格式

第一行为一个数 $n$,表示数列的长度。

接下来一行为 $n$个用空格隔开的正整数,第 $i$ 行表示数 $A_i$。

输出格式

一行一个整数,表示擦掉某些数后,最后剩下的数列中最多能有多少个数在自己的位置上,即 $A_i=i$ 最多能有多少。

输入输出样例

输入样例 #1

5
1 1 2 5 4

输出样例 #1

3

说明

对于 $20\%$ 的数据,$n\leq 20$;

对于 $60\%$ 的数据,$n\leq 100$;

对于 $100\%$ 的数据,$n\leq 10^3$。

解题思路

f[i][j]表示前i个数字删除j个数字的最优值。

对于第i个数字,如果删除,那么前面共删除j-1个数字,即:f[i][j] = f[i-1][j-1]。如果不删除,那么前面已经删除j个数字,第i个数字k可以保留下来,位置是i-j,如果跟k相等,增加1对数字。

程序实现

两种情况分别递推。

1到i-1合并在一起,特殊处理0和i(全部删除答案是0)。

f[i]由f[i-1]转移而来,每次只用到相邻两行数组,可以降维优化。

注意,删除数字的枚举,需要从大到小,因为每次更新,需要用到的是旧的(上一行)的值。

当然,也可以看成是最长不下降子序列来做,删除数字,从前往后,依次不递减。首先算出每个数字能跟编号对应,前面需要删除多少个数字。然后这些数字求满足条件的最长上升子序列。

满足条件:能删,删除数量为自然数;有数字可删,前面至少有a[i]个数字;不下降,再上一个删除的的位置删除数字不多于当前位置,且之间至少有a[i]-a[j]个数字。

洛谷P1799数列[NOI导刊]:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter