题解：P11678 [USACO25JAN] Watering the Plants P

lovely_nst · 2025-04-17 22:50:55 · 题解

P11678 Watering the Plants P

这道题我做了四天，是一道很有难度的题。~~标记打错+少判情况~~

有 n 个水池，每次可以花费 w_i 的代价让第 i 和第 i + 1 个水池的水量加 1。求最小代价使第 i 个水池中至少有 a_i 的水量。

因为 i 只能花 w_{i-1} 或 w_i 的贡献加水量，所以 w_{i-1} 和 w_i 的使用次数和不能小于 a_i。

设 f_{i,j} 为前 i-1 个水池已经锁定且满足条件，第 i 个水池目前有 j 水量的最小代价。可得转移方程：

f_{i,j}=\min_{k\ge a_{i-1}-j}f_{i-1,k} + j \times w_{i-1}

现在如何从 f_{i-1}(x) 快速转移到 f_i(x) 就是要解决的问题了。

考虑 slope trick。

可以发现，若 f_{i-1}(x) 是下凸的，f_i(x) 也是下凸的。
证明：观察转移方程可以发现其实就是求了个后缀 \min，然后再加上一个一次函数。也就是把 f_{i-1}(x) 每一对相邻点的斜率加上 w_{i-1}，因此还是下凸。

由于边界原因，i < 3 时，f_i(x) 不满足下凸性质（具体的可以看楼顶的题解）。那么就可以先预处理出 f_{i,j}(i<3)，然后再继续做。

接下来，设 L 为 f_{i-1}(x) 的最小值的位置，然后分两种情况讨论：

第一种情况可以看成把 f_{i-1}(x) 中的 [L,a_{i-1}] 这一段提取出来翻转后拼到 f_i(x) 的前缀上，后面的推平成斜率为零 0 的直线。最后全局斜率加上 w_{i-1}。

第二种情况可以看成全局重置为一条斜率为 w_{i-1} 的直线，即全局推平然后全局斜率加上 w_{i-1}。

那如何维护斜率呢？考虑使用平衡树（FHQ Treap）。

维护三个操作：

操作 1 可以参考文艺平衡树，在平衡树树上打标记，操作时下传标记。这个标记记为 tag1，表示翻转并取反该子树。

操作 2，标记 tag2 表示子树内的值全部清零。注意若打上了该标记，其他的 tag，该位的值以及子树和都要清 0。

操作 3 只需在根节点打上加的标记 tag3，之后是一样的。

注意先下传顺序是操作 2，操作 3，操作 1。原因是 tag2 标记时会把其他清零，若先下传另外两个会出问题；操作 3 是最后做的，只有下一次的下传可以影响，因此要在最后下传。

具体见代码。

记录

代码