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 表可能快不了多少，于是没有写，有兴趣的读者可以自己尝试一下。
空间可能开不下，要用滚动数组优化。
完整代码：
#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;
}
热门相关：大唐杨国舅 人心叵测 侯门弃女之妖孽丞相赖上门 魅王毒后 校花之贴身高手