讲解P1398 [NOI2013] 书法家。

使用动态规划算法，分类讨论，前缀优化。

思路：

来一篇极小常数的 \(O(N^3M)\) 和 \(O(N^2M \log^2 N)\) 的题解，最慢点在 500ms 以下但是为什么还是最劣解。

定义 \(dp_{i,j,k,x \in \{0,1,2\},y \in \{0,1,2\}}\) 表示对于正在画的第 \(x\) 个字符，目前正在画开头/中间/结尾，且当前画的矩形的右下角是 \((i,j)\) 和右上角 \((k,j)\)。

则状态转移方程为，为了使式子不过于太丑陋，分段函数就表示取 \(\max\)：

\[dp_{i,j,k,0,0} = \begin{cases} \sum\limits_{I=k}^i a_{I,j} \\ \sum\limits_{I=k}^i a_{I,j} + dp_{i,j-1,k} \end{cases}

\]

\[dp_{i,j,k,0,1} = \sum\limits_{I=k}^i a_{I,j} + \begin{cases} \max\limits_{l=i+1}^n dp_{l,j-1,k,0,0} \\ \max\limits_{x=k}^i \max\limits_{y=1}^k dp_{x,j-1,y,0,1} \\ \max\limits_{y=1}^{k-1} dp_{k-1,j-1,y} \end{cases}

\]

\[dp_{i,j,k,0,2} = \sum\limits_{I=k}^i a_{I,j} + \begin{cases} \max\limits_{l=k+1}^i dp_{i,j-1,l,0,1} \\ dp_{i,j-1,k,0,2} \end{cases}

\]

\[dp_{i,j,k,1,0} = \sum\limits_{I=k}^i a_{I,j} + \max\limits_{x=1}^n \max\limits_{z=1}^{k-2} \max\limits_{y=1}^i dp_{i,z,y,0,2}

\]

\[dp_{i,j,k,1,1} = a_{k,j} + a_{i,j} + \begin{cases} dp_{i,j-1,k,1,0} \\ dp_{i,j-1,k,1,1} \end{cases}

\]

\[dp_{i,j,k,1,2} = \sum\limits_{I=k}^i a_{I,j} + dp_{i,j-1,k,1,1}

\]

\[dp_{i,j,k,2,0} = a_{k,j} + a_{i,j} + \begin{cases} dp_{i,j-1,k,2,0} \\ \max\limits_{x=1}^n \max\limits_{z=1}^{k-2} \max\limits_{y=1}^i dp_{i,z,y,1,2} \end{cases}

\]

\[dp_{i,j,k,2,1} = \sum\limits_{I=k}^i a_{I,j} + \begin{cases} dp_{i,j-1,k,2,0} \\ dp_{i,j-1,k,2,1}\end{cases}

\]

\[dp_{i,j,k,2,2} = a_{k,j} + a_{i,j} + \begin{cases} dp_{i,j-1,k,2,1} \\ dp_{i,j-1,k,2,2} \end{cases}

\]

对于一重循环部分，可以直接前缀/后缀预处理 \(\max\)；对于查询矩阵最大值部分，可以用二维 ST 表或者暴力扫一维然后预处理另外一维的前缀/后缀 \(\max\)。

时间复杂度为 \(O(N^3M)\) 或 \(O(N^2M \log^2 N)\)，由于感觉二维 ST 表可能快不了多少，于是没有写，有兴趣的读者可以自己尝试一下。

空间可能开不下，要用滚动数组优化。

完整代码：

<code>#include<bits/stdc++.h>

#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)

#define lowbit(x) x&(-x)

#define pi pair<ll,ll>

#define pii pair<ll,pair<ll,ll>>

#define iip pair<pair<ll,ll>,ll>

#define ppii pair<pair<ll,ll>,pair<ll,ll>>

#define fi first

#define se second

#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x

#define Full(a) memset(a,0,sizeof(a))

#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);

using namespace std;

typedef double db;

typedef unsigned long long ull;

typedef int ll;

bool Begin;

const ll N=155,M=505,INF=1e9;

inline ll read(){

ll x=0,f=1;

char c=getchar();

while(c<'0'||c>'9'){

if(c=='-')

f=-1;

c=getchar();

}

while(c>='0'&&c<='9'){

x=(x<<1)+(x<<3)+(c^48);

c=getchar();

}

return x*f;

}

inline void write(ll x){

if(x<0){

putchar('-');

x=-x;

}

if(x>9)

write(x/10);

putchar(x%10+'0');

}

ll n,m,ans=-INF;

ll a[N][M],s[N][M];

ll dp[2][N][M][N];

ll MAX[M][2],T1[N][M],T2[N][M][N],T3[N][M][N],T4[N][M][N];

bool End;

int main(){

//open("A.in","A.out");

memset(T1,-0x7f,sizeof(T1));

memset(T2,-0x7f,sizeof(T2));

memset(T3,-0x7f,sizeof(T3));

memset(T4,-0x7f,sizeof(T4));

memset(MAX,-0x7f,sizeof(MAX));

memset(dp,-0x7f,sizeof(dp));

n=read(),m=read();

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

a[i][j]=read();

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

s[i][j]=s[i-1][j]+a[i][j];

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

for(int k=1;k<=i-1;k++)

dp[0][i][j][k]=s[i][j]-s[k-1][j]+max(dp[0][i][j-1][k],0);

for(int j=1;j<=m;j++){

for(int i=n;i>=1;i--){

for(int k=1;k<=i;k++){

dp[1][i][j][k]=max(T1[k-1][j-1],T2[i+1][j-1][k]);

for(int x=k;x<=i;x++)

dp[1][i][j][k]=max(dp[1][i][j][k],T3[x][j-1][k]);

dp[1][i][j][k]+=s[i][j]-s[k-1][j];

T1[i][j]=max(T1[i][j],dp[1][i][j][k]);

T2[i][j][k]=max(T2[i+1][j][k],dp[0][i][j][k]);

T3[i][j][k]=max(T3[i][j][k-1],dp[1][i][j][k]);

}

}

}

memset(dp[0],-0x7f,sizeof(dp[0]));

for(int j=1;j<=m;j++){

for(int i=1;i<=n;i++){

ll M=-INF;

for(int k=i-1;k>=1;k--){

M=max(M,dp[1][i][j-1][k+1]);

dp[0][i][j][k]=M;

dp[0][i][j][k]=max(dp[0][i][j][k],dp[0][i][j-1][k]);

dp[0][i][j][k]+=s[i][j]-s[k-1][j];

MAX[j][0]=max({MAX[j][0],MAX[j-1][0],dp[0][i][j][k]});

}

}

}

memset(dp[1],-0x7f,sizeof(dp[1]));

for(int j=5;j<=m;j++)

for(int i=1;i<=n;i++)

for(int k=1;k<=i-2;k++)

dp[1][i][j][k]=s[i][j]-s[k-1][j]+MAX[j-2][0];

memset(dp[0],-0x7f,sizeof(dp[0]));

for(int j=6;j<=m;j++)

for(int i=1;i<=n;i++)

for(int k=1;k<=i-2;k++)

dp[0][i][j][k]=a[k][j]+a[i][j]+max(dp[1][i][j-1][k],dp[0][i][j-1][k]);

memset(dp[1],-0x7f,sizeof(dp[1]));

for(int j=7;j<=m;j++){

for(int i=1;i<=n;i++){

for(int k=1;k<=i-2;k++){

dp[1][i][j][k]=s[i][j]-s[k-1][j]+dp[0][i][j-1][k];

MAX[j][1]=max({MAX[j][1],MAX[j-1][1],dp[1][i][j][k]});

}

}

}

memset(dp[0],-0x7f,sizeof(dp[0]));

for(int j=9;j<=m;j++)

for(int i=1;i<=n;i++)

for(int k=1;k<=i-2;k++)

dp[0][i][j][k]=a[k][j]+a[i][j]+max(dp[0][i][j-1][k],MAX[j-2][1]);

memset(dp[1],-0x7f,sizeof(dp[1]));

for(int j=10;j<=m;j++)

for(int i=1;i<=n;i++)

for(int k=1;k<=i-2;k++)

dp[1][i][j][k]=s[i][j]-s[k-1][j]+max(dp[0][i][j-1][k],dp[1][i][j-1][k]);

memset(dp[0],-0x7f,sizeof(dp[0]));

for(int j=11;j<=m;j++){

for(int i=1;i<=n;i++){

for(int k=1;k<=i-2;k++){

dp[0][i][j][k]=a[k][j]+a[i][j]+max(dp[1][i][j-1][k],dp[0][i][j-1][k]);

ans=max(ans,dp[0][i][j][k]);

}

}

}

write(ans);

cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";

return 0;

}