专栏文章

题解：P11678 [USACO25JAN] Watering the Plants P

llovely_nst
P11678题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipksk2x
此快照首次捕获于
2025/12/03 13:37
3 个月前
此快照最后确认于
2025/12/03 13:37
3 个月前
查看原文

P11678 Watering the Plants P

前言

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

题意

有 nn 个水池，每次可以花费 wiw_i 的代价让第 ii 和第 i+1i + 1 个水池的水量加 11。求最小代价使第 ii 个水池中至少有 aia_i 的水量。

思路

因为 ii 只能花 wi−1w_{i-1} 或 wiw_i 的贡献加水量，所以 wi−1w_{i-1} 和 wiw_i 的使用次数和不能小于 aia_i。
设 fi,jf_{i,j} 为前 i−1i-1 个水池已经锁定且满足条件，第 ii 个水池目前有 jj 水量的最小代价。可得转移方程：
fi,j=min⁡k≥ai−1−jfi−1,k+j×wi−1f_{i,j}=\min_{k\ge a_{i-1}-j}f_{i-1,k} + j \times w_{i-1}
现在如何从 fi−1(x)f_{i-1}(x) 快速转移到 fi(x)f_i(x) 就是要解决的问题了。
考虑 slope trick。
  • 可以发现，若 fi−1(x)f_{i-1}(x) 是下凸的，fi(x)f_i(x) 也是下凸的。
  • 证明：观察转移方程可以发现其实就是求了个后缀 min⁡\min，然后再加上一个一次函数。也就是把 fi−1(x)f_{i-1}(x) 每一对相邻点的斜率加上 wi−1w_{i-1}，因此还是下凸。
由于边界原因，i<3i < 3 时，fi(x)f_i(x) 不满足下凸性质（具体的可以看楼顶的题解）。那么就可以先预处理出 fi,j(i<3)f_{i,j}(i<3)，然后再继续做。
接下来，设 LL 为 fi−1(x)f_{i-1}(x) 的最小值的位置，然后分两种情况讨论：
  • L≤ai−1L\le a_{i-1} 时，因为 LL 之后的斜率单调不下降，因此 fi(j)=fi−1(ai−1−j)+j×wi−1(j≤ai−1−L)f_i(j)=f_{i-1}(a_{i-1}-j)+j\times w_{i-1}(j\le a_{i-1}-L)；当 j>ai−1−Lj>a_{i-1}-L 时，fi(j)=fi−1(L)+j×wi−1f_i(j)=f_{i-1}(L)+j\times w_{i-1}。
  • L>ai−1L> a_{i-1} 时，因为 LL 之前的斜率单调下降，因此 fi−1(L)f_{i-1}(L) 为后缀的最小值，得 fi(j)=fi−1(L)+j×wi−1f_i(j)=f_{i-1}(L)+j\times w_{i-1}。
第一种情况可以看成把 fi−1(x)f_{i-1}(x) 中的 [L,ai−1][L,a_{i-1}] 这一段提取出来翻转后拼到 fi(x)f_i(x) 的前缀上，后面的推平成斜率为零 00 的直线。最后全局斜率加上 wi−1w_{i-1}。
第二种情况可以看成全局重置为一条斜率为 wi−1w_{i-1} 的直线，即全局推平然后全局斜率加上 wi−1w_{i-1}。
那如何维护斜率呢？考虑使用平衡树（FHQ Treap）。
维护三个操作：
  1. 区间翻转并区间取反（因为反转后斜率 kk 会变成 −k-k）。
  2. 区间推平为 00。
  3. 全局加 ww。
操作 11 可以参考文艺平衡树，在平衡树树上打标记，操作时下传标记。这个标记记为 tag1tag1，表示翻转并取反该子树。
操作 22，标记 tag2tag2 表示子树内的值全部清零。注意若打上了该标记，其他的 tagtag，该位的值以及子树和都要清 00。
操作 33 只需在根节点打上加的标记 tag3tag3，之后是一样的。
注意先下传顺序是操作 22，操作 33，操作 11。原因是 tag2tag2 标记时会把其他清零，若先下传另外两个会出问题；操作 33 是最后做的，只有下一次的下传可以影响，因此要在最后下传。
具体见代码。

AC Code

记录
代码

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...