洛谷P1799数列[NOI导刊]
922+
题目大意：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]个数字。
