uva 10755 - Garbage Heap 杂

 题意就是求三维空间里和最大的一片空间的值

 输入：T//组数

A,B,C// 三个维度

T1，T2，T3……//(1,1,1),(1,1,2)……(1,2,1)每一个的值

经典的二维求区间和扩展到了三维，计算时的加加减减好繁杂，就是枚举1-2^k(k为维数) 如果有奇数个1为加法，偶数个1为减法。

 最后利用保存局部最优解，将枚举降维，n^6变n^5

 注意读入也要用long long,组之间有空行

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int A,B,C;
long long sum[22][22][22];
#define inf 17179869184001ll  //2^31 * 20^3 + 1
long long calc(int x1,int x2,int y1,int y2,int z1,int z2)
{
    return sum[x2][y2][z2]-sum[x1][y2][z2]-sum[x2][y1][z2]-sum[x2][y2][z1]+sum[x1][y1][z2]+sum[x1][y2][z1]+sum[x2][y1][z1]-sum[x1][y1][z1];
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        long long ans=-inf,tmp;
        scanf("%d%d%d",&A,&B,&C);
        memset(sum,0,sizeof(sum));
        int i,j,k;
        for(i=1;i<=A;i++)
            for(j=1;j<=B;j++)
                for(k=1;k<=C;k++)
                {
                    scanf("%lld",&tmp);
                    sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]+sum[i][j][k-1]-sum[i-1][j-1][k]-sum[i-1][j][k-1]-sum[i][j-1][k-1]+sum[i-1][j-1][k-1]+tmp;
                    //二进制001-111 有奇数个1时为+，偶数个为-，可以推广到高维
                }
        for(int x1=0;x1<A;x1++)
         for(int y1=0;y1<B;y1++)
          for(int x2=x1+1;x2<=A;x2++)
           for(int y2=y1+1;y2<=B;y2++)
           {
            long long before=0;
            for(int z=1;z<=C;z++)//利用before降维
            {
                tmp=calc(x1,x2,y1,y2,0,z);
                ans=max(ans,tmp-before);
                before=min(before,tmp);
            }
           }
        printf("%lld\n",ans);
        if(T)puts("");
    }
}