题解

思路

只考虑最后保留下来的玉米。若相邻两株保留玉米之间有某次区间操作在此结束，把这个操作向右延长不会破坏已经满足的单调不下降关系。因此，总能把方案规范化为：沿保留序列从左到右，每株玉米得到的增量单调不减，且都在 $[0,K]$ 内。反过来，任意这样的增量序列都能用若干个后缀区间操作实现。

令 $f_{i,j}$ 表示以第 $i$ 株玉米结尾、且它得到 $j$ 次增高时的最长保留序列。若前一株是 $p<i$，其增量为 $q$，则必须满足

所以需要在二维偏序中查询最大 DP 值。

做法

按原下标从左到右处理玉米。使用二维树状数组维护坐标 $(a_i+j,j)$ 上的最大 $f_{i,j}$，支持矩形前缀最大值查询。对同一株玉米按 $j=K,K-1,\ldots,0$ 的顺序处理，避免当前玉米刚写入的较小增量状态被自己重复使用：

随后把 $f_{i,j}$ 更新到点 $(a_i+j,j)$。所有状态中的最大值即为答案。

当 $K=1$ 时，只有增量 $0$ 和 $1$ 两层，可分别用两个一维树状数组完成相同转移。

当 $n\le100$ 时，可为每个位置预处理各增量状态的前缀最大值。枚举前驱位置 $p$ 和当前增量 $j$，合法的前驱增量上界为 $\min(j,a_i+j-a_p)$，从此前缀最大值中直接转移，复杂度为 $O(n^2K)$。

证明

先证明规范化。若某次区间操作在两株相邻保留玉米之间结束，将其右端点延长到序列末尾，只会增加后面保留玉米的高度，不会使已有的单调不下降关系失效。逐次延长后，每次操作在保留序列上都是一个后缀，因此各株得到的增量单调不减。其最大值不超过操作次数 $K$。反之，对任意非降增量序列，在增量每次上升的位置开始一个后缀操作，恰能实现它，操作数等于末尾增量且不超过 $K$。

于是，一个合法前驱状态恰好满足 $p<i$、$q\le j$ 和 $a_p+q\le a_i+j$。二维树状数组的前缀查询精确枚举这两个偏序条件中的全部已处理状态。倒序枚举 $j$ 又保证结构中只有更早位置的合法状态。因此转移既不漏解也不引入非法解，最终最大值就是最优保留株数。

复杂度

• 时间复杂度：$O(nK\log(5000+K)\log(K+1))$；
• 空间复杂度：$O((5000+K)(K+1))$。