Uva10755

在题中的A*B*C的矩形中，当确定X1，X2,Y1，Y2时，1->z的子矩形的和为

sum[x2][y2][1] -(sum[x1-1][y2][1] + sum[x2][y1-1][1] -sum[x1-1][y1-1][1] + sum[x2][y2][z+1] - sum[x1-1][y2][z+1] -sum[x2][y1-1][z+1] + sum[x1-1][y1-1][z+1]);

sum[x][y][z]指的是，以(x,y,z)为右下角的矩形的和

sum[x][y][z]的递推公式为 sum[k][j][i] = (sum[k-1][j][i] + sum[k][j-1][i] -sum[k-1][j-1][i] + sum[k][j][i+1] - sum[k-1][j][i+1] -sum[k][j-1][i+1] + sum[k-1][j-1][i+1] + d[k][j][i]);

本题最后结果可能会很大，所以ans的初值要赋值为最小的longlong

#include<bits/stdc++.h>

#define inf 0x3f3f3f3f

const int maxn=20;

using namespace std;

typedef long long ll;

int t;

int a,b,c;

ll d[maxn+10][maxn+10][maxn+10];

ll sum[maxn+10][maxn+10][maxn+10];

int main()
{
        scanf("%d",&t);
        while(t--){
                memset(d, 0 ,sizeof(d));
                memset(sum,0,sizeof(sum));
                scanf("%d%d%d",&a,&b,&c);
                for(int i = 1; i <= a; i++){
                        for(int j = 1; j <= b; ++j){
                                for(int k = 1; k <= c; ++k){
                                        scanf("%lld",&d[i][j][k]);
                                }
                        }
                }

                for(int i = c; i >= 1; --i){
                        for(int j = 1; j <= b; ++j){
                                for(int k = 1; k <= a; ++k){
                                       sum[k][j][i] = (sum[k-1][j][i] + sum[k][j-1][i] -
                                       sum[k-1][j-1][i] + sum[k][j][i+1] - sum[k-1][j][i+1] -
                                       sum[k][j-1][i+1] + sum[k-1][j-1][i+1] + d[k][j][i]);
                                }
                        }
                }

                ll ans = -(ll)((1LL)<<63);
                for(int x1 = 1; x1 <= a; ++x1){
                        for(int x2 = x1; x2 <= a; ++x2){
                                for(int y1 = 1; y1 <= b; ++y1){
                                        for(int y2 = y1; y2 <= b; ++y2){
                                                ll min_sumz = 0;
                                                for(int z = 1; z <= c; ++z){
                                                        ll temp = sum[x2][y2][1] -
                                       (sum[x1-1][y2][1] + sum[x2][y1-1][1] -
                                        sum[x1-1][y1-1][1] + sum[x2][y2][z+1] - sum[x1-1][y2][z+1] -
                                        sum[x2][y1-1][z+1] + sum[x1-1][y1-1][z+1]);
                                                        ans = max(ans, temp - min_sumz);
                                                        min_sumz = min(min_sumz, temp);
                                                }
                                        }
                                }
                        }
                }

                printf("%lld
",ans);
                if(t){
                        printf("
");
                }
        }
    return 0;
}