题意：有一个长方体，有Ａ＊Ｂ＊Ｃ（我们算做长宽高吧）小块组成，每块小块有它的价值，正负都行，问找一块子长方体，价值最大；思路：首先我们要先预处理价值g[i][j][k],表示从高为k,即第k层长到ｉ，宽到ｊ那一块总价值；我们可以知道g[i][j][k] += g[i-1][j][k] + g[i][j-1][k] – g[i-1][j-1][k];意思就是这一块的价值，等于长减一那一块，加上宽减一那一块，这时候中间算了两次，所以要减掉中间；知道这个之后我们就可以枚举Ａ，Ｂ的起点和终点；然后递推计算Ｃ的起点和终点去何值是价值最大；其中ｓｕｍ函数表示以枚举出的长宽，，计算出endC这一层的价值，在endC++,计算下一层，叠加；如果叠加后的结果是负的，那么就要从startC那一层开始，一层层往下减，知道变为正的，或者全部都减掉位置（这里和最大连续和是一样的）；这样我们就把三维化为二维，知道每一层的价值，去算最大连续和：
#include<cstdio>#include<cstring>#include<algorithm>#define ll long longusing namespace std;const ll INF = (ll)1 << 60;const int N = 25;ll g[N][N][N];int a,b,c;ll sum(int startA, int endA, int startB, int endB, int C) {return g[endA][endB][C] – g[startA – 1][endB][C] – g[endA][startB – 1][C] + g[startA – 1][startB – 1][C];}int main() {int t;scanf("%d",&t);while(t–) {memset(g, 0 , sizeof(g));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",&g[i][j][k]);g[i][j][k] += (g[i – 1][j][k] + g[i][j – 1][k] – g[i – 1][j – 1][k]);}}}ll ans = -INF;for(int startA = 1 ; startA <= a ; startA++) {for(int endA = startA ; endA <= a ;endA++) {for(int startB = 1; startB <= b; startB++) {for(int endB = startB ; endB <= b; endB++) {int startC = 1;int endC = 1;ll m = 0;while(endC <= c) {m += sum(startA, endA, startB, endB, endC);if(m > ans)ans = m;while(m < 0 && startC <= endC) {m -= sum(startA, endA, startB, endB, startC);startC++;if(startC <= endC && m > ans)ans = m;}endC++;}}}}}printf("%lld\n",ans);if(t)printf("\n");}}
记录沿途的心情。那样的生活才是我想要的。
