【题解】UVa 10755【Garbage Heap】

分析

这里就是三维前缀和的应用,将一个$O(n^9)$的算法降到$O(n^6)$,强势AC。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define foreach(i,s,t) for(int i = (s);i <= (t);++i)
using std::min;using std::max;
typedef long long int64;
void expand(int i,int &b0,int &b1,int &b2){
    b0 = i & 1;i >>= 1;
    b1 = i & 1;i >>= 1;
    b2 = i & 1;
}

int sign(int b0,int b1,int b2){return (b0 + b1 + b2) % 2 == 1 ? 1 : -1;}

const int MAXN = 30 + 6;
const int64 INF = 1LL << 60;
int64 S[MAXN][MAXN][MAXN];

int64 sum(int x1,int x2,int y1,int y2,int z1,int z2){
    int dx = x2 - x1 + 1,dy = y2 - y1 + 1,dz = z2 - z1 + 1;
    int64 s = 0;
    for(int i = 0;i < 8;i++){
        int b0,b1,b2;
        expand(i,b0,b1,b2);
        s -= S[x2 - b0 * dx][y2 - b1 * dy][z2 - b2 * dz] * sign(b0,b1,b2);
    }
    return s;
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        int a,b,c,b0,b1,b2;scanf("%d %d %d",&a,&b,&c);
        memset(S,0,sizeof(S));
        foreach(x,1,a) foreach(y,1,b) foreach(z,1,c) scanf("%lld",&S[x][y][z]);
        foreach(x,1,a) foreach(y,1,b) foreach(z,1,c) foreach(i,1,7){
            expand(i,b0,b1,b2);
            S[x][y][z] += S[x - b0][y - b1][z - b2] * sign(b0,b1,b2);
        }
        int64 ans = -INF;
        foreach(x1,1,a) foreach(x2,x1,a) foreach(y1,1,b) foreach(y2,y1,b){
            int64 M = 0;
            foreach(z,1,c){
                int64 s = sum(x1,x2,y1,y2,1,z);
                ans = max(ans,s - M);
                M = min(M,s);
            }
        }
        printf("%lld\n",ans);
        if(T) printf("\n");
    }

    return 0;
}

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注