给一个长度为N的序列，请删除尽量少的数，使得新序列中满足第I个数为I条件的数最多。
Input
第一行有一个正整数N。 第二行有N个正整数Ai，表示原序列中第I个数为Ai。
Output
只有一个整数ANS,表示最多能有多少个数满足条件。
首先不难发现,i-ai<0的数是肯定不能归位的,然后我们忽略他. 最直观的一个想法就是动态规划,设 fi,j 为在原序列第i个位置,删了j个数的最大收益 然后也不难发现,删的个数肯定是某个i-ai,所以我们将方程改一改,变成 fi 表示将i放到原位所获得的最大收益. 不难看出有 fi=max(fk)+1 ,k表示上一个放到原位的是哪个位置
然后我们再来看k需要满足什么条件 好像需要满足 i−a[i]>=k−a[k] 后面需要删的必须比前面的多,不然就会删过头… 然后没啥条件了啊… 那不是可以直接线段树维护差值,然后单点修改区间查询? YES这题我切了! b(￣▽￣)d
.
. . .
. .
那你就太too young too simple了,难道你就没有发现,还有一个条件 a[i]>a[k] 吗 (代码打到一半) (°o°；)… 那怎么办,方了 (其实根据某神牛的分析,这个条件是完全可以忽略的,因为满足上面那个条件就必定满足这个条件,只不过线段树常数太大估计只能拿80分,我蒟蒻不会…)
其实 fi=max(fk)+1 不就是等价于i-a[i]的最长不下降子序列么 但还有一种特殊情况就是,有数个为i的位置,这些位置必然有大有小,但我们只能取一个. 怎么办呢? 其实我们按倒序排一下他的i-a[i],这样每一种就最多会取下一个了 然后nlogn dp,就可以解决这题了
