题意：给出一个三维的由单位立方体组成的长方体，每个单位立方体有一个值，求这个大的长方体的一个子长方体，使得构成它的单位立方体对应的值之和最大。
分析：这是经典问题从一维延伸到三维的情况。画图后就能解决~构造前缀和a[i][j][k]表示以它为右下角的立方体和，然后枚举，复杂度O（n6），这道题目肯定能过。
代码：
View Code
1 #include <stdio.h> 2 #include <algorithm> 3 using namespace std; 4 long long a[21][21][21]; 5 int main(){ 6 int cas, line = 0; 7 scanf("%d", &cas); 8 while(cas--){ 9 int n, m, p, i, j, k, x, y, z; 10 scanf("%d%d%d", &n, &m, &p); 11 for(i=1; i<=n; i++) for(j=1; j<=m; j++) for(k=1; k<=p; k++) 12 scanf("%lld", &a[i][j][k]); 13 for(i=1; i<=n; i++) for(j=1; j<=m; j++) for(k=1; k<=p; k++) 14 a[i][j][k]+=a[i][j][k-1]; 15 for(i=1; i<=n; i++) for(j=1; j<=m; j++) for(k=1; k<=p; k++) 16 a[i][j][k]+=a[i][j-1][k]; 17 for(i=1; i<=n; i++) for(j=1; j<=m; j++) for(k=1; k<=p; k++) 18 a[i][j][k]+=a[i-1][j][k]; 19 long long ans = -0x3f3f3f3f3f3fll; 20 for(i=0; i<n; i++) for(j=0; j<m; j++) for(k=0; k<p; k++) 21 for(x=i+1; x<=n; x++) for(y=j+1; y<=m; y++) for(z=k+1; z<=p; z++) 22 ans = max(ans, a[x][y][z]-a[i][j][k] + a[i][j][z]-a[i][y][z] + a[i][y][k]-a[x][y][k] + a[x][j][k]-a[x][j][z]); 23 if(line++) printf("\n"); 24 printf("%lld\n", ans); 25 } 26 return 0; 27 }
发现如果不包含algorithm头文件max函数报错~
