A上C(20,2)卡上下界...B上C(20,2)卡上下界...在C的方向上做一維的最大連續字串問題...這樣把3維的最大子矩陣問題就轉化為1維的了...
預處理...sum[ x ] [ y ] [ z ] 代表在z這個二維平面上...(1,1)和(x,y)分別為對角坐標的矩陣的所有數之和....
Program:
[cpp]
//http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1696
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<map>
#include<algorithm>
#define ll long long
#define oo 2000000000
using namespace std;
int A,B,C;
ll sum[22][22][22];
ll getsum(int As,int Ae,int Bs,int Be,int C)
{
return sum[Ae][Be][C]-sum[As-1][Be][C]-sum[Ae][Bs-1][C]+sum[As-1][Bs-1][C];
}
int main()
{
int T,t,i,j,k,As,Ae,Bs,Be,Cs,Ce;
ll m,ans;
cin>>T;
for (t=1;t<=T;t++)
{
cin>>A>>B>>C;
memset(sum,0,sizeof(sum));
for (i=1;i<=A;i++)
for (j=1;j<=B;j++)
for (k=1;k<=C;k++)
{
cin>>sum[i][j][k];
sum[i][j][k]+=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k];
}
ans=-oo;
ans*=10000;
for (As=1;As<=A;As++)
for (Ae=As;Ae<=A;Ae++)
for (Bs=1;Bs<=B;Bs++)
for (Be=Bs;Be<=B;Be++)
{
Cs=Ce=1;
m=0;
while (Ce<=C)
{
m+=getsum(As,Ae,Bs,Be,Ce);
if (m>ans) ans=m;
while (m<0 && Cs<=Ce)
{
m-=getsum(As,Ae,Bs,Be,Cs);
Cs++;
if (Cs<=Ce && m>ans) ans=m; //保證至少一個矩陣
}
Ce++;
}
}
if (t!=1) cout<<endl;
cout<<ans<<endl;
}
return 0;
}
/*
1
2 3 3
21 -39 4 -39 4 -44 1 -32 -25 -35 2 17 6 10 2 -12 -22 35
ans 55
1
1 2 2
-38 40 21 -34
ans 40
*/
//http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1696
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<map>
#include<algorithm>
#define ll long long
#define oo 2000000000
using namespace std;
int A,B,C;
ll sum[22][22][22];
ll getsum(int As,int Ae,int Bs,int Be,int C)
{
return sum[Ae][Be][C]-sum[As-1][Be][C]-sum[Ae][Bs-1][C]+sum[As-1][Bs-1][C];
}
int main()
{
int T,t,i,j,k,As,Ae,Bs,Be,Cs,Ce;
ll m,ans;
cin>>T;
for (t=1;t<=T;t++)
{
cin>>A>>B>>C;
memset(sum,0,sizeof(sum));
for (i=1;i<=A;i++)
for (j=1;j<=B;j++)
for (k=1;k<=C;k++)
{
cin>>sum[i][j][k];
sum[i][j][k]+=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k];
}
ans=-oo;
ans*=10000;
for (As=1;As<=A;As++)
for (Ae=As;Ae<=A;Ae++)
for (Bs=1;Bs<=B;Bs++)
for (Be=Bs;Be<=B;Be++)
{
Cs=Ce=1;
m=0;
while (Ce<=C)
{
m+=getsum(As,Ae,Bs,Be,Ce);
if (m>ans) ans=m;
while (m<0 && Cs<=Ce)
{
m-=getsum(As,Ae,Bs,Be,Cs);
Cs++;
if (Cs<=Ce && m>ans) ans=m; //保證至少一個矩陣
}
Ce++;
}
}
if (t!=1) cout<<endl;
cout<<ans<<endl;
}
return 0;
}
/*
1
2 3 3
21 -39 4 -39 4 -44 1 -32 -25 -35 2 17 6 10 2 -12 -22 35
ans 55
1
1 2 2
-38 40 21 -34
ans 40
*/
