算法题：uva 10755 - Garbage Heap（三维最大子矩阵）

算法题：uva 10755 - Garbage Heap（三维最大子矩阵）2014-03-17 csdn博客 shuangde800题目链接:

http://uva.onlinejudge.org/index.php？ option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=1696

和二维的最大子矩阵的思想是一样的，只是变成了三维的。

枚举层数的上下界，然后把上下界之间的所有层“压缩”成一层，在这“一层”上用二维的方法再计算。

注意用long long

代码：

#include<cstdio>#include<cstring>#include<iostream>#include<cctype>using namespace std;typedef long long int64 ;const int MAXN = 25;int A, B, C;int64 cube[MAXN][MAXN][MAXN];inline int64 read_int64（）{char ch = getchar（）;while（！isdigit（ch） && ch！="-"） ch=getchar（）;bool neg = false;if（ch == "-"） neg=true, ch=getchar（）;int64 ans=0;while（isdigit（ch））{ans = ans*10+ch-"0";ch = getchar（）;}if（neg） return -ans;return ans;}inline void input（）{scanf（"%d%d%d", &A,&B,&C）;memset（cube, 0, sizeof（cube））;for（int k=1; k<=A; ++k）{for（int i=1; i<=B; ++i）{for（int j=1; j<=C; ++j）{cube[k][i][j] = read_int64（）;cube[k][i][j] += cube[k][i][j-1]-cube[k][i-1][j-1]+cube[k][i-1][j] - （cube[k-1][i][j-1]-cube[k-1][i-1][j-1]+cube[k-1][i-1][j]） + cube[k-1][i][j];} //列} //行}//层}int64 solve（）{// 枚举层数的上下界int64 ans = -2147483647-1;for（int down=0; down<A; ++down）{for（int up=down+1; up<=A; ++up）{// 枚举层上的“行”for（int d=0; d<B; ++d）{ for（int u=d+1; u<=B; ++u）{int64 minx = 0;for（int k=1; k<=C; ++k）{ int64 sum = （cube[up][u][k]-cube[down][u][k]）- （cube[up][d][k]-cube[down][d][k]）;ans = max（ans, sum-minx）;if（sum < minx） minx=sum;}}}}}return ans;}int main（）{int nCase;scanf（"%d", &nCase）;while（nCase--）{input（）; cout << solve（） << endl;if（nCase）putchar（"
"）;}return 0;}