【白书训练指南】（UVa10755）Garbage Heap

先po代码，之后把我那几个不太明了的知识点讲讲，巩固以下。三维的扫描线算法想要掌握还真是有一定的难度的。

代码

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#define FOR(i,s,t) for(int i=(s);i<=(t);++i)

using namespace std;

typedef long long ll;

const ll INF=1ll<<60;

const int maxn=25;

inline void expand(int i, int& b0, int& b1,int& b2)

{

    b0=i&1; i>>=1;

    b1=i&1; i>>=1;

    b2=i&1;

    return;

}

inline int sign(int b0,int b1,int b2)

{

    return (b0+b1+b2)%2?1:-1;

}

ll heap[maxn][maxn][maxn];

ll 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;

    ll s=0;

    for(int i=0;i!=8;++i)

    {

        int b0,b1,b2;

        expand(i,b0,b1,b2);

        s-=heap[x2-b0*dx][y2-b1*dy][z2-b2*dz]*sign(b0,b1,b2);

    }

    return s;

}

int main()

{

    int T; cin>>T;

    while(T--)

    {

        memset(heap,0,sizeof(heap));

        int a,b,c,b0,b1,b2;

        cin>>a>>b>>c;

        FOR(i,1,a) FOR(j,1,b) FOR(k,1,c) cin>>heap[i][j][k];

        FOR(i,1,a) FOR(j,1,b) FOR(k,1,c) FOR(p,1,7)

        {

            expand(p,b0,b1,b2);

            heap[i][j][k]+=heap[i-b0][j-b1][k-b2]*sign(b0,b1,b2);//?????

        }

        ll ans=-INF;

        FOR(x1,1,a) FOR(x2,x1,a) FOR(y1,1,b) FOR(y2,y1,b)

        {

            ll tmpM=0;

            FOR(z,1,c)

            {

                ll s=sum(x1,x2,y1,y2,1,z);

                ans=max(ans,s-tmpM);

                tmpM=min(tmpM,s);

            }

        }

        cout<<ans<<endl;

        if(T) cout<<endl;

    }

    return 0;

}

巴特西

【白书训练指南】（UVa10755）Garbage Heap

代码

最新文章

热门文章