[dp] [数据结构] P3287 [SCOI2014] 方伯伯的玉米田

_Cheems · 2023-10-24 17:06:42 · 个人记录

题意

传送门

给出一个序列，你可以选取任意一段区间并加 1，至多进行 k 次操作。求所有操作后的最长不下降序列长度？

思路

硬做显然不可行，不妨先看看每次操作 [l,r]：

• 设区间 [s,t] 最长不下降序列长度为 A[s,t]。
• 操作前后 A[l,r] 不变。
• 操作前后 A[1,r] 不减、A[l,n] 不增。
• 所以操作 [l,r] 一定劣于操作 [l,r+1]。

于是有结论：最优解中，每次操作的右端点一定为 n。这样就能 \rm dp 了。

（证明不是特别严谨）

那么设 f_{i,ki} 表示到 i 位时，已经拔高 ki 次，最长不下降序列长度。

朴素 \rm dp：暴力进行转移，对于所有 j<i 且 a_j + kj \le ai+ki，f_{i,ki} = \max(f_{j,kj} + 1)。

可恶的出题人不给一点暴力分

考虑优化：显然，决策集合的元素只增不减，那么考虑维护该集合即可加速转移，可以用二维树状数组实现。

注意树状数组的 k 值域需整体右移一位，因为有 0。

提交记录