p14267

题解里我把原题中的横纵坐标调换了，例如

(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,0}=\max\limits_{k=1}^j \sum\limits_{k\le l\le j} a_{i,l}+\color{blue}\max\limits_{k=1}^i\sum\limits_{k\le l<i}a_{l,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 种花差不多.

文章操作