题解：P11678 [USACO25JAN] Watering the Plants P

对一个位置浇水会影响到其相邻的水量，因此令 $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)$，需要大力卡常。