UVA 10755 Garbage Heap 三维最大子矩阵和 -

题目地址：http://vjudge.net/problem/UVA-10755

像基础的一维，二维，根据前缀和能求出所有的体积，在得到后直接枚举就好了

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
typedef long long LL;
const LL maxn=20+3,INF=(1LL<<60);
LL n,S[maxn][maxn][maxn]; //S[i][j][k] 记录(1,1,1)->(i,j,k)的体积
void Expend(int i,int& a,int& b,int& c){a=i&1; i>>=1;b=i&1; i>>=1;c=i&1;
}
int inline sign(int a,int b,int c){return (a+b+c)&1?1:-1;  //符号为什么这么变 ，画个图就知道了
}
LL sum(int x1,int x2,int y1,int y2,int z1,int z2){int dx=x2-x1+1,dy=y2-y1+1,dz=z2-z1+1;LL s=S[x2][y2][z2];REP(i,1,7){int a,b,c;Expend(i,a,b,c);s-=S[x2-a*dx][y2-b*dy][z2-c*dz]*sign(a,b,c);}return s;
}
int main(int argc, char const *argv[])
{int T,x0,y0,z0,a,b,c; scanf("%d",&T);while(T--){scanf("%d%d%d",&a,&b,&c);memset(S,0,sizeof(S));REP(i,1,a) REP(j,1,b) REP(k,1,c) {scanf("%lld",&S[i][j][k]);REP(l,1,7){Expend(l,x0,y0,z0);S[i][j][k]+=S[i-x0][j-y0][k-z0]*sign(x0,y0,z0); //递推出S[i][j][k]}}LL ans=-INF;REP(x1,1,a) REP(x2,x1,a) REP(y1,1,b) REP(y2,y1,b){ //固定住x,y, LL M=0;    REP(z,1,c){   //求出在此范围内 最大和LL Sum=sum(x1,x2,y1,y2,1,z);ans=max(ans,Sum-M);M=min(M,Sum);   //用M保存最小，可以免得枚举z1~z2}}printf("%lld\n", ans);if(T) putchar('\n');}return 0;}