BZOJ 3594 [Scoi2014] 方伯伯的玉米田

发布于 2017-08-18  126 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3594

https://loj.ac/problem/2211

题意:一个序列,最多 k 次选择一段区间加一,求最长单调不下降子序列。


首先有一个结论...k 次操作的右端点选择 n 一定是最优方案之一

假设我们选了 r,那么把 r 换成 n 一定不会更劣,因为这并没有改变 [r+1,n] 的大小关系,所以都选 n 一定是最优解之一。

那么可以写 dp 式了:\(dp_{i,j}=max(dp_{x,y})+1\)

其中\(x< i , y\leqslant j ,a_x+y\leqslant a_i+j\)

三维偏序问题,可以上二维树状数组了。

有一个小问题是内层循环枚举应该倒序,因为同层 i 是无法更新答案的,或者可以先正序枚举再将同层的一起 updata

 


一个非常弱的准退役OIER