UVa 10755 Garbage Heap 三维前缀和 求最大子长方体和

题目给出一个长方体, 每个格子有一个值

现求一个子长方体, 使得其包含的方块的值的和最大.

采取枚举上下界, 配合3维前缀和即可在O(n ^ 5)的时间内求解.

枚举x1, x2(x的上下界), 枚举y1, y2(y的上下界), 之后O(n)对该段z的前缀和处理, 找出最大的子段.

 

# include <iostream>
# include <cstring>
# include <algorithm>
# define rep(x, s, t) for (int x = (s); x <= (t); ++x )

using namespace std;

const int maxn = 30;
const long long INF = 1LL<<60;
int a, b, c;
long long S[maxn][maxn][maxn];

inline void expand(int i, int&b0, int& b1, int &b2)
{
    b0 = i&1; i >>= 1;
    b1 = i&1; i >>= 1;
    b2 = i&1;
}

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

long long 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;
    long long s = 0;
    rep(i, 0, 7)
    {
        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;
    cin >> T;
    while (T--)
    {
        int b0, b1, b2;
        cin >> a >> b >> c;
        memset(S, 0, sizeof S);
        rep(x, 1, a) rep(y, 1, b) rep(z, 1, c) cin >> S[x][y][z];
        rep(x, 1, a) rep(y, 1, b) rep(z, 1, c)
            rep(i, 1, 7)
            {
                expand(i, b0, b1, b2);
                S[x][y][z] += S[x-b0][y-b1][z-b2] * sign(b0, b1, b2);
            }

        long long ans = -INF;

        rep(x1, 1, a) rep(x2, x1, a) rep(y1, 1, b) rep(y2, y1, b)
        {
            long long M = 0;
            rep(z, 1, c)
            {
                long long s = sum(x1, x2, y1, y2, 1, z);
                ans = max(ans, s - M);
                M = min(M, s);
            }
        }
        cout << ans << endl;
        if (T) cout << endl;
    }
    return 0;
}

发表评论

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

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>