756
技術社區[雲棲]
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("");
}
}
最後更新：2017-04-03 12:54:36