题目给出一个长方体, 每个格子有一个值
现求一个子长方体, 使得其包含的方块的值的和最大.
采取枚举上下界, 配合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;
}