Sol P8490

直接令 $f_{i,j}$ 表示前 $i$ 列，第 $i$ 列修高度为 $j$ 的长堤最大重量是很不好转移的，因为你没办法知道 $i-1$ 列的鱼是否已经计算过贡献了。

可以发现，如果钦定第 $i$ 列的鱼只能被其左边或只能被其右边的长堤抓住是不影响答案的，因为如果一个鱼被左边（或右边）的长堤抓住，则这一列高度低于这条鱼的鱼同样能被左边（或右边）的长堤抓住。

令 $f(i,j,0/1)$ 表示第 $i$ 列修的长堤长度为 $j$，钦定第 $i$ 列只能被其左边（或右边）的长堤抓住，前 $i$ 列抓住的鱼最大重量，$W_{x,y}$ 表示第 $x$ 行第 $y$ 列的鱼重量（如果没有鱼则 $W_{x,y}$ 视为 $0$）则有：

这是 $O(n^3)$ 的，考虑优化。

观察转移式子，$\mathrm{I,II,V,VI}$ 可以双指针直接维护，对于 $\mathrm{III}$，当 $j\gets j-1$ 时，对于 $k>j$ 的部分，上面这坨式子的值会增加 $W_{i,j-1}$，这个相当于后缀加求后缀 $\max$，直接上线段树总复杂度是 $O(n\log n)$ 的，实际上可以 $O(n)$，而且比线段树好写，但是做的时候犯唐了没想到（），$\mathrm{IV,VII}$ 和 $\mathrm{III}$ 思路是类似的，前缀加前缀 $\max$。

可以发现长堤要么修到 $N$，要么恰好修到鱼下面一格，证明就是如果原来第 $i$ 列长堤长度为 $j$ 且 $(i,Y)$ 有鱼且到 $(i,j)$ 到 $(i,Y-1)$ 均没有鱼，则可以让 $j\gets Y$，此时不影响第 $i$ 列抓住的鱼，但旁边两列有可能抓住更多的鱼。这样可以把 $j$ 的有效状态数减少到 $O(n+m)$，结合前面的优化，复杂度 $O((n+m)\log (n+m))$。

然后还有一点常数优化，根据 $f(i,j,0/1)$ 的定义显然 $f(i,j,0)>f(i,j,1)$，$\mathrm{I}$ 可以把 $f(i-1,j,1)$ 部分删去，$\mathrm V$ 也可以删去。