C++14(g++5.4) 解法, 执行用时: 729ms, 内存消耗: 608K, 提交时间: 2019-07-28 12:53:22
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
#define maxn 50
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef double db;
int a[maxn+5][maxn+5],sl[maxn+5][maxn+5];
int dp[2][3][3];
int main()
{
int n,m; scanf("%d%d",&n,&m);
rep(i,1,n) rep(j,1,m) scanf("%d",&a[i][j]);
rep(i,1,n) rep(j,1,m) sl[i][j]=sl[i-1][j]+a[i][j];
int ans=0;
rep(d1,1,n) rep(u1,d1,n) rep(d2,d1,n) rep(u2,d2,n)
{
int u=min(u1,u2),d=max(d1,d2);
memset(dp[0],0,sizeof dp[0]);
rep(i,1,m)
{
int b[2][2]={};
b[1][0]=sl[u1][i]-sl[d1-1][i];
b[0][1]=sl[u2][i]-sl[d2-1][i];
b[1][1]=b[1][0]+b[0][1]-(u>=d?2*(sl[u][i]-sl[d-1][i]):0);
dp[i&1][0][1]=max(0,dp[i-1&1][0][1])+b[0][1];
dp[i&1][0][2]=max(dp[i-1&1][0][1],dp[i-1&1][0][2]);
dp[i&1][1][0]=max(0,dp[i-1&1][1][0])+b[1][0];
dp[i&1][1][1]=max(max(0,dp[i-1&1][1][0]),max(dp[i-1&1][0][1],dp[i-1&1][1][1]))+b[1][1];
dp[i&1][1][2]=max(max(dp[i-1&1][0][1],dp[i-1&1][0][2]),max(dp[i-1&1][1][1],dp[i-1&1][1][2]))+b[1][0];
dp[i&1][2][0]=max(dp[i-1&1][1][0],dp[i-1&1][2][0]);
dp[i&1][2][1]=max(max(dp[i-1&1][1][0],dp[i-1&1][1][1]),max(dp[i-1&1][2][0],dp[i-1&1][2][1]))+b[0][1];
dp[i&1][2][2]=max(max(dp[i-1&1][1][1],dp[i-1&1][1][2]),max(dp[i-1&1][2][1],dp[i-1&1][2][2]));
}
rep(i,0,2) rep(j,0,2) if(ans<dp[m&1][i][j]) ans=dp[m&1][i][j];
}
printf("%d\n",ans);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 708ms, 内存消耗: 604K, 提交时间: 2019-07-28 18:35:26
#include <bits/stdc++.h>
using namespace std;
int a[55][55],sl[55][55];
int dp[2][3][3];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
sl[i][j]=sl[i-1][j]+a[i][j];
}
}
int ans=0;
for(int d1=1;d1<=n;d1++){
for(int u1=d1;u1<=n;u1++){
for(int d2=d1;d2<=n;d2++){
for(int u2=d2;u2<=n;u2++){
int u=min(u1,u2),d=max(d1,d2);
memset(dp[0],0,sizeof(dp[0]));
for(int i=1;i<=m;i++){
int b[2][2]={};
b[1][0]=sl[u1][i]-sl[d1-1][i];
b[0][1]=sl[u2][i]-sl[d2-1][i];
b[1][1]=b[1][0]+b[0][1]-(u>=d?2*(sl[u][i]-sl[d-1][i]):0);
dp[i&1][0][1]=max(0,dp[i-1&1][0][1])+b[0][1];
dp[i&1][0][2]=max(dp[i-1&1][0][1],dp[i-1&1][0][2]);
dp[i&1][1][0]=max(0,dp[i-1&1][1][0])+b[1][0];
dp[i&1][1][1]=max(max(0,dp[i-1&1][1][0]),max(dp[i-1&1][0][1],dp[i-1&1][1][1]))+b[1][1];
dp[i&1][1][2]=max(max(dp[i-1&1][0][1],dp[i-1&1][0][2]),max(dp[i-1&1][1][1],dp[i-1&1][1][2]))+b[1][0];
dp[i&1][2][0]=max(dp[i-1&1][1][0],dp[i-1&1][2][0]);
dp[i&1][2][1]=max(max(dp[i-1&1][1][0],dp[i-1&1][1][1]),max(dp[i-1&1][2][0],dp[i-1&1][2][1]))+b[0][1];
dp[i&1][2][2]=max(max(dp[i-1&1][1][1],dp[i-1&1][1][2]),max(dp[i-1&1][2][1],dp[i-1&1][2][2]));
}
for(int i=0;i<=2;i++){
for(int j=0;j<=2;j++){
if(ans<dp[m&1][i][j])ans=dp[m&1][i][j];
}
}
}
}
}
}
printf("%d\n",ans);
}
grid, each cell has a value 
, you can choose at most two rectangles such that sum of values of the cell belonging to 
one rectangle is maximized.
where 
and 
. Then, the rectangle is composed of all the cell (x, y) where 
and 
.