传送门
题意
给你一个 \(n\) 行 \(m\) 列的矩阵，要求对于每行选出一个区间 \([l_i, r_i]\)，得到 \(\sum _ {j = {l_i}} ^ {r_i} a_{i, j}\) 的权值。
区间之间有限制：
\[\exists j, j \in [l_{i - 1}, r_{i - 1}], j \in [l_i, r_i]
\]
\[\exists j, j \not \in [l_{i - 1}, r_{i - 1}], j \in [l_i, r_i]
\]
求最大权值。
思路
显然这是一个 dp 题。
考虑朴素的状态设计 \(f_{i, l, r}\) 表示计算了前 \(i\) 行，第 \(i\) 行选区间 \([l, r]\) 的最大权值。
显然状态数 \(O(nm^2)\) 直接倒闭。
我们试图转换题目限制，可以发现，相当于是限制 \(l_{i - 1}, r_{i - 1}\) 至少有一个在区间 \((l_i, r_i)\) 中。
那也就是说，我们没有必要记录左右端点，于是得到状态优化：
\(f_{i, j, 0/1}\) 表示计算前 \(i\) 行，第 \(i\) 行选择的左（\(0\)）/ 右（\(1\)）端点是 \(j\)，此时的最大权值。
可以启发想到这一点的例子：
设 \(i - 1\) 行的左右端点分别是 \(l', r'\)，第 \(i\) 行左右端点是 \(l, r\)。
考虑情况 \(l \lt l'\)，则 \(r\) 的限制只有 \(r \ge l'\)，显然没有必要记录 \(r'\)，可以启发优化状态。
接下来就是分类讨论：
case 1: \(l \lt l'\)
此时要求满足 \(r \ge l'\)。
\[f_{i,l,0} = \max _ {l' = l + 1} ^ m f_{i - 1, l', 0} + calc1(l, l')
\]
其中 \(calc1(l, r)\) 表示所有区间 \([L,R], L = l, R \ge r\) 中 \(\sum _ {j = L} ^ R a_j\) 最大的值。
\[calc1(l,r) = \max _ {j = r} ^ m \left( s_j - s_{l - 1} \right)
\]
\[\begin{align}
calc1(l,r) = \max _ {j = r} ^ m \left( s_j - s_{l - 1} \right) \\
= \max _ {j = r} ^ m \left( s_j \right) - s_{l - 1}
\end{align}
\]