这篇文章上次修改于 687 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
0x01 简化题意
给你一个立方体，要求从这个立方体中切割出一个小的立方体使得立方体内的和最大。
0x02 思路分析
思来想去，实在是没有什么好算法在立方体上，于是我们又想到了老朋友——前缀和，但是且慢，一维的前缀和很好理解，二维的前缀和可以画图，你让我在考场上怎么分析三位前缀和，难道还能搭积木？（bushi
0x03 三位前缀和
不要慌，我们可以归纳大法—— $dp$ 为前缀和， $ans$ 为区间 $a$ 为原数组。
一维前缀和: $dp_i=a_i+dp_{i-1}$
二位前缀和: $dp_{i~j}=dp_{i-1~j}+dp_{i~j-1}-dp_{i-1~j-1}+a_{i~j}$
仔细观察，再看。
每一次先把每一维分别减 $1$ , 加到答案上，再选择 $2$ 维减 $1$ ,从答案中减去。
其实这就是在处理这些区间的重叠部分，一加一减，三维前缀和呼之欲出：
$dp_{i~j~k}=dp_{i-1~j~k}+dp_{i~j-1~k}+dp_{i~j~k-1}-dp_{i-1~j-1~k}-dp{i-1~j~k-1}-dp_{i~j-1~k-1}+dp_{i-1~j-1~k-1}+a_{i~j~k}$
好的，所以怎么计算答案，继续归纳：
一维前缀和：$ans_{i~j}=dp_i-dp_j$
二位前缀和: $ans_{i~j~x~y}=dp_{x~y}-dp_{i-1~y}-dp_{x~j-1}+dp_{i-1~j-1}$
一加一减，非常有序，直接推三维:
$dp_{i~j~k~x~y~z}=dp_{x~y~z}-dp_{i-1~y~z}-dp_{x~j-1~z}-dp_{x~y~k-1}+dp_{i-1~j-1~z}+dp_{i-1~y~k-1}+dp_{x~j-1~k-1}-dp_{i-1~j-1~k-1}$
接下来直接暴力枚举区间，$O(n^6)$ 刚好能过。
0x04 上代码
//注意细节，不要复制题解
#include <iostream>
#include <cstdio>
#define int long long
inline int read();
int map[25][25][25];
signed mian(){
freopen("garbageheap.in","r",stdin);
freopen("garbageheap.out","w",stdout);
int t=read();
while(t--){
int a=read(),b,c;
b=read();
c=read();
for(int i=1;i<=a;i++){
for(int j=1;j<=b;j++){
for(int m=1;m<=c;m++){
map[i][j][m]=read();
map[i][j][m]+=map[i-1][j][m]+map[i][j-1][m]+map[i][j][m-1]-map[i-1][j-1][m]-map[i-1][j][m-1]-map[i][j-1][m-1]+map[i-1][j-1][m-1];
}
}
}
int _max=-0x3f3f3f3f3f3f3f3f;
for(int i=1;i<=a;i++){
for(int j=1;j<=b;j++){
for(int m=1;m<=c;m++){
for(int ai=i;ai<=a;ai++){
for(int bj=j;bj<=b;bj++){
for(int bm=m;bm<=c;bm++){
_max=std::max(_max,map[ai][bj][bm]-map[i-1][bj][bm]-map[ai][j-1][bm]-map[ai][bj][m-1]+map[i-1][j-1][bm]+map[i-1][bj][m-1]+map[ai][j-1][m-1]-map[i-1][j-1][m-1]);
}
}
}
}
}
}
printf("%lld\n",_max);
if(t!=0){
putchar('\n');
}
}
return 114514;
}
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
0x05 后话
这篇题解真长，三维的前缀和从二维和一维中是很好推出来的，另外，UVA的数据非常毒瘤，每两组数据之间要输出两个换行，最后一个却不能输出换行。