吃西瓜[matrix.pas/c/cpp]

[说明]此题中出现的所有数全为整数

[背景]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部分

[输入][matrix.in]

首行三个数h,m,n(注意顺序),分别表示西瓜的高,长,宽.

以下h部分,每部分是一个m*n的矩阵,第i部分第j行的第k个数表示西瓜第i层,第j行第k列的那块1立方厘米的小正方体的营养值.

 

[输出][matrix.out]

SubRaY所能得到的最大营养值

 

[样例输入]

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

 

[样例输出]

45

 

[数据范围]

对于30%的数据,h=1,1<=m,n<=10

对于全部的数据,1<=h<=32,1<=m,n<=50,保证h<=m,n

 

[解题思路]

这是一道很恶心有用的题目，我对此表示非常恶心开心，所以在这里发一下题解。

这道题目用到了压缩的方法，其具体方法是想象一下切面包吧将这个句型沿竖直方向切成一片一片地，分别求出每一片中最大的长方体的数值，将其压缩入一个f[j]中，最后利用f[j]求解答案。

其中，要用到一个sum数组来存储前k层前i行的第j列的总和，用sunp[k,i,j]表示，sum可以在一开始读入数据中就可以得出。

接着，我用要枚举k,kk[分别为层数的起点和终点]，i,ii[行数的起点与终点],j[列数]，求出第k到第kk层，第i到第ii行，第j列的长方体的最大数值，方程如下：

cc:=sum[kk,ii,j]-sum[kk,i-1,j]-sum[k-1,ii,j]+sum[k-1,i-1,j];学过容斥原理吧，差不多一个道理。

于是我们就可以用f[j]=max(f[j-1]+cc,cc)求出起最大值

附上标称[pascal]

var
    a:array[1..50,1..50,1..50]of longint;
    sum:array[0..50,0..50,0..50]of longint;
    i,j,k,kk,ii,jj,l,h,m,n,cc,ans:longint;
    f:array[0..50]of longint;
function max(x,y:longint):longint;
begin
    if x>y then exit(x) else exit(y);
end;
begin
    readln(h,m,n);
    for k:=1 to h do
        for i:=1 to m do
            for j:=1 to n do
            begin
                read(a[k,i,j]);
                sum[k,i,j]:=sum[k,i-1,j]+a[k,i,j];
            end;
    for k:=1 to h do
        for i:=1 to m do
            for j:=1 to n do
            begin
                sum[k,i,j]:=sum[k,i,j]+sum[k-1,i,j];
            end;
    for k:=1 to h do
        for kk:=k to h do
            for i:=1 to m do
                for ii:=i to m do
                    for j:=1 to n do
                    begin
                        cc:=sum[kk,ii,j]-sum[kk,i-1,j]-sum[k-1,ii,j]+sum[k-1,i-1,j];
                        f[j]:=max(f[j-1]+cc,cc);
                        if f[j]>ans then ans:=f[j];
                    end;
    writeln(ans);
end.

然后，有节操才怪的邱宇豪又要出来炫耀展示劳动成果了：