题解：P11678 [USACO25JAN] Watering the Plants P

Aegleseeker_ · 2025-10-15 18:20:14 · 题解

对一个位置浇水会影响到其相邻的水量，因此令 f_{i,j} 代表考虑到 [1,i]，前 i 个位置都浇完水且向 i+1 额外 贡献了 j 的水量的最小代价，再令 g_{i,j} 代表 f 的后缀 \min，即 g_{i,j}=\min\limits_{k\ge j}f_{i,k}，则第 i 个位置的答案为 g_{i-1,w_i}。

转移为 f_{i,j}=\min\limits_{j+k\ge w_i}f_{i-1,k}+c_ij，即 f_{i,j}=g_{i-1,\max(0,w_i-j)}+c_ij。直接做是 O(nV) 的，考虑优化。

使用整体 dp 维护 g_{i,j}，重新写一下 f_{i} 的转移：对于 j\le w_i，f_{i,j}=g_{i-1,w_i-j}+c_ij，这等价于将原来 [0,w_i] 的 g 值翻转，然后加上斜率为 c_i 的线段；对于 j>w_i，f_{i,j}=g_{i-1,0}+c_ij，这等价于将原来 [w_i+1,V] 区间推平，然后加上斜率为 c_i 的线段。由于维护的是 g，因此最后还需要对每个后缀 chkmin。

前面几个操作可以上平衡树，对于加斜率为 c_i 的线段，我们不妨转换一步，维护 g'_{i,j}=g_{i,j}-g_{i,j-1} 即 g 的差分，这样就变成区间加了；对于区间翻转，转换为先区间和求出翻转后最靠前的位置，然后翻转 [l+1,r] 再整体取相反数即可。需要分别维护区间加、区间乘、区间推平、区间翻转。但是最后一个操作后缀 chkmin 还没有解决，这个基本上不太好从数据结构上优化，考虑一些 slope trick：事实上经过整体 dp 的转换不难证明 f 的下凸性，即 g 的差分数组具有单调性。于是 chkmin 一次后我们维护的东西一定是一个平台加上一段单调的区间，可以每次按值分裂出拐点，然后前缀推平即可。

复杂度 O(n\log V)，需要大力卡常。