uva 10755 - Garbage Heap(三维最大子矩阵)-白红宇

uva 10755 - Garbage Heap(三维最大子矩阵)

阅读量：4072 次

发布时间：2019-05-25

本文共 1166 字，大约阅读时间需要 3 分钟。

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

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

注意用long long

代码：

#include
   
    #include
    
     #include
     
      #include
      
       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