Skip to content

1002 二哥种花生

题目

Description

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

Input Format

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

第2行至第L+1行,每行有W个整数,分别表示对应的单位面积上的花生产量A( \( 0 \leq 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 \leq L,W \leq 100 \);

对于100%的数据: \( 1 \leq L,W \leq 1000 \)。

全部区域大小满足:\( 1 \leq a \leq L ,1 \leq b \leq W \) 。

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/19.
//
// 多重滑动窗口

#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;

constexpr int N = 1000 + 5;
int height[N][N];

int main() {
    int l, w;
    cin >> l >> w;
    for (int i = 0; i < l; ++i) {
        for (int j = 0; j < w; ++j) {
            scanf("%d", &height[i][j]);
        }
    }
    int a, b;
    cin >> a >> b;
    int X = l - a + 1, Y = w - b + 1;

    int chunk[N]{};
    for (int i = 0; i < a; ++i) {
        for (int j = 0; j < b; ++j) {
            chunk[0] += height[i][j];
        }
    }

    int currentAns = chunk[0];

    for (int y = 1; y < Y; ++y) {
        chunk[y] = chunk[y - 1];
        for (int i = 0; i < a; ++i) {
            chunk[y] += height[i][y + b - 1];
            chunk[y] -= height[i][y - 1];
        }
        currentAns = max(currentAns, chunk[y]);
    }

    for (int x = 1; x < X; ++x) {
        for (int y = 0; y < Y; ++y) {
            for (int j = 0; j < b; ++j) {
                chunk[y] += height[x + a - 1][j + y];
                chunk[y] -= height[x - 1][j + y];
            }
            currentAns = max(currentAns, chunk[y]);
        }
    }

    cout << currentAns << endl;
    return 0;
}

CallMeInk's solution

#include<iostream>
using namespace std;

int main()
{
    int n,m,x,y,ans,sum;
    int a[1005][1005],f[1005][1005] ;
    cin >> n >> m;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            cin >> a[i][j];
    cin >> x >> y;

    for (int i=1;i<=n;i++)
        f[0][i] = 0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            f[i][j] = f[i-1][j] + a[i][j];

    ans = 0;
    for (int i=1;i<=n-x+1;i++)
    {
        sum = 0;
        for (int k=1;k<=y;k++)
            sum += f[i+x-1][k] - f[i-1][k];
        if (sum > ans) ans = sum;
        for (int j=2;j<=m-y+1;j++)
        {
             sum += f[i+x-1][j+y-1]-f[i-1][j+y-1]-(f[i+x-1][j-1]-f[i-1][j-1]);
             //cout << i << ' ' << j << ' ' << sum << endl;
             if (sum > ans) ans = sum;
        }
        //cout << "ans=" << ans << endl;
    }
    cout << ans << endl;
}

LuminousXLB's solution

// 1002. 二哥种花生
// #552773 正确 / 分数:100 / 时间:2778ms / 内存:16624kb 

#include <iostream>

using namespace std;

int main()
{
    // freopen("input.txt", "r", stdin);

    int l, w;
    cin >> l >> w;

    char area[1001][1001];
    short tmp = 0;

    for (int i = 0; i < l; i++) {
        for (int j = 0; j < w; j++) {
            cin >> tmp;
            area[i][j] = tmp;
        }
    }

    int a, b;
    int cnt, res = 0;
    cin >> a >> b;

    if (a == 1 && b == 1) {
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < w; j++) {
                if (area[i][j] > res) {
                    res = area[i][j];
                }
            }
            if (res == 9) {
                break;
            }
        }
    } else if (a == l && b == w) {
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < w; j++) {
                res += area[i][j];
            }
        }
    } else {
        for (int si = 0; si <= l - a; si++) {
            cnt = 0;
            for (int i = 0; i < a; i++) {
                for (int j = 0; j < b; j++) {
                    cnt += area[i + si][j];
                }
            }

            if (cnt > res) {
                res = cnt;
            }

            for (int sj = 1; sj <= w - b; sj++) {
                for (int i = 0; i < a; i++) {
                    cnt -= area[si + i][sj - 1];
                    cnt += area[si + i][sj - 1 + b];
                }

                if (cnt > res) {
                    res = cnt;
                }
            }
        }
    }
    cout << res;

    return 0;
}

FineArtz's solution

/* 二哥种花生 */
#include <iostream>
using namespace std;

int sum[1005][1005] = {0};

int main(){

    int m, n, t;
    cin >> m >> n;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j){
            cin >> t;
            sum[i][j] = t + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    int a, b, ans = 0;
    cin >> a >> b;
    for (int i = a; i <= m; ++i)
        for (int j = b; j <= n; ++j)
            ans = max(ans, sum[i][j] - sum[i - a][j] - sum[i][j - b] + sum[i - a][j - b]);
    cout << ans << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

int hs[1009][1009] = { 0 };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int L, W;
    cin >> L >> W;

    for (int i = 1; i <= L; ++i) {
        for (int j = 1; j <= W; ++j) {
            int temp;
            cin >> temp;
            hs[i][j] = hs[i][j - 1] + hs[i - 1][j] - hs[i - 1][j - 1] + temp;
        }
    }
    int cur_ans = 0;
    int a, b;
    cin >> a >> b;
    for (int i = 0; i + a <= L; ++i) {
        for (int j = 0; j + b <= W; ++j) {
            if (hs[i + a][j + b] - hs[i][j + b] - hs[i + a][j] + hs[i][j] > cur_ans)
                cur_ans = hs[i + a][j + b] - hs[i][j + b] - hs[i + a][j] + hs[i][j];
        }
    }

    cout << cur_ans;

    return 0;
}

victrid's solution

//1002 rewrite cf FineArtz
#include <iostream>

using namespace std;

int main()
{
    int m, n;
    cin >> m >> n;
    //DynMat    Name:Summat
    //Lines:m+1 rows:n+1
    int **Summat = new int *[m + 1];
    for (int i = 0; i < m + 1; i++)
        *(Summat + i) = new int[n + 1]();
    int *Summat_cfg = new int(m + 1);
    //End of Dynmat.
    int getnum;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            cin >> getnum;
            Summat[i][j] = getnum + Summat[i - 1][j] + Summat[i][j - 1] - Summat[i - 1][j - 1];
        }
    int l, h;
    cin >> l >> h;
    int max = 0;
    int total = 0;
    for (int i = 0; i < m + 1 - l; i++)
        for (int j = 0; j < n + 1 - h; j++)
        {
            total = (Summat[i + l][j + h] + Summat[i][j] - Summat[i + l][j] - Summat[i][j + h]);
            max = total > max ? total : max;
        }
    cout << max;
    //Release DynMat
    //Name:Summat
    for (int i = 0; i < *Summat_cfg; i++)
        delete[] * (Summat + i);
    delete[] Summat;
    delete Summat_cfg;
    //End of Release.
    return 0;
}