算法竞赛训练指南，54 页， 三维的前缀和
本题要点：
1、 定义前缀和：
将长方体切片（按z左边）， 每一片就是一个平面;
sum[i][j][k]平面上[1,1]到[i][j]在高度为 z == k 时的区域前缀和;
二维的前缀和公式：
sum(x, y) = array[x][y] + sum(x - 1, y) + sum(x, y - 1) - sum(x - 1, y - 1)
2、求解最大和 的子 长方体：
遍历底面的左边范围 [x1, x2], [y1, y2] （此时相当于固定了底面）， 在遍历 第z 层，
pre： 表示 以第 z - 1 层 结尾的 子长方体 的最大和。
tmp： 表示 当前层（第z层）子长方体 的 和；
如果 pre > 0, 以第 z 层 结尾的 子长方体 的最大和 为 tmp + pre， 否则 为 tmp;
最后， 用 ans 不断更新 ans = max(ans, tmp)即可。
3、 注意使用 long long 来存储每一个点的值
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MaxN = 25;
const LL INF = 1LL << 60;
int A, B, C, Test;
LL sum[MaxN][MaxN][MaxN];// sum[i][j][k]平面上[1,1]到[i][j]在高度为k时的区域前缀和LL getSum(int x1, int x2, int y1, int y2, int z)
{
return sum[x2][y2][z] - sum[x2][y1 - 1][z] - sum[x1 - 1][y2][z] + sum[x1 - 1][y1 - 1][z];
}void solve()
{
LL ans = -INF, pre = 0, tmp; 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)// 相当于固定了 x，y坐标， 长方体的底面在 区域[x1, x2], [y1, y2]范围内{
pre = 0;for(int z = 1; z <= C; ++z){
tmp = getSum(x1, x2, y1, y2, z); if(pre > 0) {
tmp += pre;}pre = tmp;ans = ans > tmp ? ans : tmp;}}printf("%lld\n", ans);
}int main()
{
scanf("%d", &Test);LL val;while(Test--){
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", &val);// long longsum[i][j][k] = val + sum[i - 1][j][k] + sum[i][j - 1][k] - sum[i - 1][j - 1][k];}solve();if(Test){
printf("\n");}}return 0;
}/* 1 2 2 2 -1 2 0 -3 -2 -1 1 5 *//* 6 */