?
10755 - Garbage Heap Time limit: 3.000 seconds |
最大子立方体和比最大子矩阵多一维，同样转换为一维，然后求最值。
#include
#include
#include
#define ll long long #define inf 1ll<<60//加ll using namespace std; ll sum[27][27][27]; ll getsum(int x1,int x2,int y1,int y2,int z)//求从x1到x2，y1到y2在z轴上的数字之和 { return sum[x2][y2][z]-sum[x1-1][y2][z]-sum[x2][y1-1][z]+sum[x1-1][y1-1][z]; } int main() { int t,cas=1,flag; scanf(%d,&t); flag=t; while(t--) { int a,b,c; scanf(%d%d%d,&a,&b,&c); memset(sum,0,sizeof(sum)); for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) for(int k=1;k<=c;k++) { scanf(%lld,&sum[i][j][k]); sum[i][j][k]+=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k];//预处理得到在k这个平面上前矩阵（i，j）的和 } ll maxx=-inf; for(int sx=1;sx<=a;sx++)//x方向开始位置 for(int ex=sx;ex<=a;ex++)//x方向结束位置 for(int sy=1;sy<=b;sy++)//y方向开始位置 for(int ey=sy;ey<=b;ey++)//y方向结束位置 { ll ans=0; for(int sz=1,ez=1;ez<=c;ez++)//遍历z轴 { ans+=getsum(sx,ex,sy,ey,ez); maxx=max(maxx,ans); while(ans<0&&sz<=ez) { ans-=getsum(sx,ex,sy,ey,sz); sz++; if(sz<=ez&&ans>maxx)maxx=ans; } } } printf(%lld ,maxx); if(cas!=flag)printf( ); cas++; } }