hoj 2555 三维最大子段和
枚举底面的小矩形。#include <stdio.h>#include <cstring>int sum[33][51][51],f[51],a[33][51][51];int main(){ int h,n,m,t,max,ans; while(scanf("%d%d%d",&h,&n,&m)==3) { memset(sum,0,sizeof(sum)); for(int i=1; i<=h; i++) { for(int j=1; j<=n; j++) for(int k=1; k<=m; k++) { scanf("%d",&a[i][j][k]); t=0; for(int p=1; p<=j; p++) for(int q=1; q<=k; q++) t+=a[i][p][q]; sum[i][j][k]=t; } } max=-1000000000; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) for(int p=i; p<=n; p++) for(int q=j; q<=m; q++) { ans=0; for(int k=1; k<=h; k++) { t=sum[k][p][q]+sum[k][i-1][j-1]-sum[k][i-1][q]-sum[k][p][j-1]; if(ans>0) ans+=t; else ans=t; if(ans>max) max=ans; } } printf("%d\n",max); } return 0;}