SJTU 1002二哥种花生 原题地址

题目描述

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

输入格式

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

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

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

输出格式

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

示例输入

1
2
3
4
5
6

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

示例输出

1

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 。 #思路一

• 看到这道题之后我的第一反应是创建一个二维数组，用来储存每单位面积上的花生产量，然后遍历枚举计算出最大值，于是很快写出了代码。

  思路一代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

//author:husama
#include<stdio.h>
int main()
{
    int L=0, W=0;
    int l, w,result=0,temp=0;
    scanf("%d %d",&L,&W);//输入花生地的长和宽
    int **matrix= new int*[L];  //定义矩阵数组
    for (int i = 0; i < L; ++i)  matrix[i] = new int[W];
    for (int i = 0; i < L; ++i)
    {
        for (int j = 0; j < W; ++j)
            scanf("%d",&matrix[i][j]);
    }
    scanf("%d %d",&l,&w);//获得目标区块的大小
    //遍历计算
    for (int m =0; m < W-w+1; ++m)
    {
        for (int n = 0; n< L-l+1; ++n)
        {
            temp = 0;
            for (int i = n; i < n+l; ++i)
            {
                for (int j = m; j < m+w; ++j)
                {
                    temp += matrix[i][j];
                }
            }
            if (result <= temp)result = temp;
        }
    }
    printf("%d",result);
    for (int i = 0; i < L; ++i)
        delete[]matrix[i];
    delete[] matrix;
    return 0;
}

四层for循环嵌套，时间复杂度太高，不过我还是去试了试，结果当然是超时。必须想个更简洁的算法。

思路二（改进）

• 第一次做oj题，显示出了基础的不扎实，无奈只能去参考别人的思路。 看了这个博客顿时开窍。 在遍历枚举的过程中，其实每向右移动一格，矩形内只有最左边的一列被删除并仅新增了最右的一列，如图：
• 
• 变成 这个过程中中间蓝色框部分的数据是不变得：
• 

所以当采用思路一的做法时，多计算了很多次！ 而且,每次枚举时都要用两个for循环嵌套求出框中数字之和 怎样改进呢,我们可以改进这个矩阵的储存方式，即：

每个矩阵单元储存以1, 1为左上角，i, j为右下角的矩形内数字之和

采用这种存储方式的好处在于，如果要取得以x1, y1为左上角 x2, y2为右下角的矩形内数字之和，只需计算 matrix[x2][y2] -matrix[x1 - 1][y2] - matrix[x2][y1 - 1] + matrix[x1 - 1][y1 - 1] 即可,示意图如下：

• 蓝色部分的面积=红色-绿色-黄色+黄绿相交 这样就解决了枚举时内部还要用两个for循环嵌套求出框中数字之和的问题，而用普通的四则运算代替！时间复杂度大大降低。

  思路二代码：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

  //author:husama #include <stdio.h> int main() { int L=0,W=0,l=0,w=0; int result=0,temp=0,temp_2=0; int **matrix;//储存以1, 1为左上角，i, j为右下角的矩形内数字之和 scanf("%d %d",&L,&W); matrix=new int* [L]; for (int i=0; i<L; i++) { matrix[i]=new int[W]; for (int j=0; j<W; j++) { scanf("%d",&temp); if(i>0&&j>0) matrix[i][j]=matrix[i-1][j]+matrix[i][j-1]-matrix[i-1][j-1]+temp; else if(i==0&&j>0) matrix[0][j]=matrix[0][j-1]+temp; else if(i>0&&j==0) matrix[i][0]=matrix[i-1][0]+temp; else matrix[0][0]=temp; } } scanf("%d %d",&l,&w); for (int i=l-1; i<L; i++) for (int j=w-1; j<W; j++ ) { if ( i !=l-1&&j != w-1) temp_2=matrix[i][j] - matrix[i - l][j] - matrix[i][j-w] +matrix[i-l][j-w]; else if (i == l-1&& j != w-1) temp_2=matrix[l-1][j]-matrix[l-1][j-w]; else if (i != l-1 && j == w-1) temp_2=matrix[i][w-1]-matrix[i-l][w-1]; else temp_2=matrix[l-1][w-1]; if(temp_2>=result) result=temp_2; } printf("%d",result); for (int i = 0; i < L; ++i) delete[] matrix[i]; delete[] matrix; return 0; }

  终于AC了!