P3287 [SCOI2014] 方伯伯的玉米田

标签：log 树状 P3287 玉米 玉米田 SCOI2014

首先每次选择的区间结尾都可以换成 \(n\)，仍然保持单调不降，我们就按这个策略拔高玉米。

令 \(f_{i,j}\) 表示 \(1\sim i\) 这段前缀进行了 \(j\) 次操作，第 \(i\) 株玉米不被拔掉，所能剩下最多的玉米数量：

\[f_{i,j}=\max\{f_{p,q}|p<i,q<j,a_p+q\leq a_i+j\}+1 \]

枚举 \(i\)，剩下两个限制用二维树状数组维护即可。

有一个小细节，操作次数可能为 \(0\)，扔进树状数组时需要加 \(1\)。

时间复杂度 \(O(nK\log K\log(a+K))\)。

标签：log,树状,P3287,玉米,玉米田,SCOI2014
From： https://www.cnblogs.com/landsol/p/17707403.html