Sol P8490
Nygglatho
·
·
题解
直接令 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）则有：
\begin{aligned}
f(i,j,0)=\max\{\\
&\max(f(i-1,j,0),f(i-1,j,1))\qquad\qquad\qquad\ \ \ \ \ \mathrm{I}\\
&\max\limits_{k<j}\{f(i-1,k,0)\},\qquad\qquad\qquad\qquad\qquad\qquad\mathrm{II}\\
&\max\limits_{k>j}\{f(i-1,k,0)+\sum\limits_{j\le y<k}W_{i,y}\},\qquad\qquad\qquad\mathrm{III}\\
&\max\limits_{k<j}\{f(i-1,k,1)+\sum\limits_{k\le y<j}W_{i-1,y}\}\qquad\qquad\qquad\mathrm{IV}\\
\}\\
f(i,j,1)=\max\{\\
&f(i-1,j,1)\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\mathrm{V}\\
&\max\{f(i-1,k,0)\},\qquad\qquad\qquad\qquad\qquad\qquad\ \,\mathrm{VI}\\
&\max\limits_{k<j}\{f(i-1,k,1)+\sum\limits_{k\le y<j}W_{i-1,y}\}\qquad\qquad\qquad\mathrm{VII}\\
\}
\end{aligned}
这是 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 也可以删去。
Submission