?
題目：
SubRaY有一天得到一塊西瓜,是長方體形的....
SubRaY發現這塊西瓜長m厘米,寬n厘米,高h厘米.他發現如果把這塊西瓜平均地分成m*n*h塊1立方厘米的小正方體,那么每一小塊都會有一個營養值(可能為負,因為西瓜是有可能壞掉的,但是絕對值不超過200).
現在SubRaY決定從這m*n*h立方厘米的西瓜中切出mm*nn*hh立方厘米的一塊小西瓜(一定是立方體形,長寬高均為整數),然后吃掉它.他想知道他最多能獲得多少營養值.(0<=mm<=m,0<=nn<=n,0<=hh<=h.mm,nn,hh的值由您來決定).
換句話說,我們希望從一個m*n*h的三維矩陣中,找出一個三維子矩陣,這個子矩陣的權和最大.
?
一個2*3*4的例子,最優方案為切紅色2*3*1部分
輸入格式 Input Format
首行三個數h,m,n(注意順序),分別表示西瓜的高,長,寬.
以下h部分,每部分是一個m*n的矩陣,第i部分第j行的第k個數表示西瓜第i層,第j行第k列的那塊1立方厘米的小正方體的營養值.
輸出格式 Output Format
SubRaY所能得到的最大營養值
樣例輸入 Sample Input
2 3 4
4 1 2 8
0 5 -48 4
3 0 1 9
2 1 4 9
1 0 1 7
3 1 2 8
樣例輸出 Sample Output
45
時間限制 Time Limitation
1s
注釋 Hint
對于30%的數據,h=1,1<=m,n<=10
對于全部的數據,1<=h<=32,1<=m,n<=50,保證h<=m,n
來源 Source
noip 模擬賽
?
因為數據比較小，所以不會超時的。你先處理下這一層這個位置和上個位置的累加和，然后在處理每一列的累加和。
然后每次運算只用從左開始往右進行累加，算的就是一個矩陣了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; int a[52][52][52]; int c[52][52][52]; int b[1000]; int p[1000]; int main() {int h,m,n;//高，長，寬cin>>h>>m>>n;for(int w=1;w<=h;w++){for(int i=1;i<=m;i++){for(int j=1;j<=n;j++)cin>>a[w][i][j],c[w][i][j]=a[w][i][j];}}for(int w=1;w<=h;w++){for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){c[w][i][j]+=c[w-1][i][j];}}}for(int w=1;w<=h;w++){for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){c[w][i][j]+=c[w][i-1][j];}}}/*cout<<endl;for(int w=1;w<=h;w++){for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){cout<<c[w][i][j]<<' ';}cout<<endl;}}*/int ans=0;for(int w=1;w<=h;w++)//第幾層 {for(int H=1;H<=w;H++)//w層上面選幾層 {for(int i=1;i<=m;i++)//第i行 {for(int t=1;t<=i;t++)//這行上面的t行 {memset(b,0,sizeof(b));memset(p,0,sizeof(p));for(int k=1;k<=n;k++)//從左往右加 {p[k]=c[w][i][k]-c[H-1][i][k]-c[w][t-1][k]+c[H-1][t-1][k];b[k]=max(b[k-1]+p[k],p[k]);if(b[k]>ans)ans=b[k];}}}}}cout<<ans<<endl;return 0; }
?
)
