p14267

Nygglatho · 2025-10-21 09:31:19 · 题解

题解里我把原题中的横纵坐标调换了，例如 (y_1,x_3) 表示第 y_1 行第 x_3 列，a 表示原数组.

DP.

考虑把图分成三部分，第一部分最右边为 x_3，第二部分最右边 x_4，第三部分 x_2.

令 f_{i,j,0/1/2} 表示 (y_1,x_3)/(y_1,x_4)/(y_1,x_2) 在 (i,j) 的最大值.

则有：

• - $f_{i,j,1}=\max\limits_{k=1}^{j-1}\left\{dp_{i,k,0}+\sum\limits_{k<l\le j}a_{i,l}\right\}+\color{blue}\max\limits_{k=1}^i\sum\limits_{k\le l<i}a_{l,j}+\max\limits_{k=i}^n\sum\limits_{l<i\le k}a_{l,j}$. - $f_{i,j,2}=\max\limits_{k=1}^{j}\left\{dp_{i,k,1}+\sum\limits_{k<l\le j}a_{i,l}\right\}$.

令 n,m 同阶，直接用前缀和维护可以 O(n^3).

可以发现蓝色这一部分是独立的，只和 j 有关，并且是一个最大子段和类似的东西，先单独算.

然后前面这一部分就维护前缀 max 即可，每次加 a_{i,j} 之后和 a_{i,j}/f_{i,j,0}/f_{i,j,1} 取 max.

复杂度 O(nm).

感觉和 NOIP2022 T1 种花差不多.

Submission