上交OJ-1002. 二哥种花生

1002.二哥种花生

---

Description

二哥在自己的后花园里种了一些花生，也快到了收获的时候了。这片花生地是一个长度为L、宽度为W的矩形，每个单位面积上花生产量都是独立的。他想知道，对于某个指定的区域大小，在这么大的矩形区域内，花生的产量最大会是多少。

Input Format

第1行有2个整数，长度L和宽度W。

第2行至第L+1行，每行有W个整数，分别表示对应的单位面积上的花生产量A（ 0≤A<10 ）。

第L+2行有2个整数，分别是指定的区域大小的长度a和宽度b。

Output Format

输出一个整数m，表示在指定大小的区域内，花生最大产量为m。

Sample Input

4 5
1 2 3 4 5
6 7 8 0 0
0 9 2 2 3
3 0 0 0 1
3 3

Sample Output

38

样例解释

左上角：38 = (1+2+3) + (6+7+8) + (0+9+2)

数据范围
对于30%的数据： 1≤L,W≤100；

对于100%的数据： 1≤L,W≤1000。

全部区域大小满足：1≤a≤L，1≤b≤W 。

分析

此问题为求大矩阵中固定大小子矩阵和最大值。
最简单的思路是，直接遍历求和每个子矩阵。其需要3个loop迭代，有重复计算，开销超时。
因此，需要保留中间结果。
一个子矩阵（a,b）对应右下角位置（A,B），其和为：

sum[A][B]-sum[A-a][B]-sum[A][B]+sum[a][b]

因此，在输入时就可以计算这个中间结果，并保留。
然后只需要2个loop迭代即可算出结果。

#include <stdio.h>

int main()
{
    int L,W;
    int a,b;
    int nut[1000][1000];
    int tmp;
    int i,j;
    int sum=0;
    scanf("%d%d",&L,&W);
    for(i=0;i<L;i++) {
        for(j=0;j<W;j++) {
            scanf("%d",&tmp); //输入时计算中间结果
            if(i>0 && j>0) nut[i][j]=tmp+nut[i-1][j]+nut[i][j-1]-nut[i-1][j-1];
            else if(i==0 && j>0) nut[i][j]=nut[i][j-1]+tmp;
            else if(j==0 && i>0) nut[i][j]=nut[i-1][j]+tmp;
            else nut[i][j]=tmp;
        }
    }
    scanf("%d%d",&a,&b);
    for(i=a-1; i<L; i++) {
        for(j=b-1;j<W;j++) { //两重遍历
            if(i==a-1 && j==b-1) tmp=nut[i][j];
            else if(i==a-1 && j!=b-1) tmp=nut[i][j]-nut[i][j-b];
            else if(i!=a-1 && j==b-1) tmp=nut[i][j]-nut[i-a][j];
            else tmp=nut[i][j]-nut[i-a][j]-nut[i][j-b]+nut[i-a][j-b];
            if (tmp>sum) sum=tmp;
        }
    }
    printf("%d",sum);
    return 0;
}