一.题目链接:

HDU-1559

二.题目大意:

给出一个 m × n 的矩阵,和一个大小为 x × y 的子矩阵,求子矩阵的最大值为多少?

三.分析:

利用前缀和求出 顶点 到 每个点 矩阵的和,然后枚举子矩阵顶点的位置即可.

如图:

四.代码实现:

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define PI acos(-1.0)
#define ll long long int
using namespace std;

const int M = 1010;
int sum[M][M];

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        memset(sum, 0, sizeof(sum));
        int m, n, x, y;
        int data;
        scanf("%d %d %d %d", &m, &n, &x, &y);
        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                scanf("%d", &data);
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + data;
            }
        }
        int ans = 0;
        for(int i = 1; i + x - 1 <= m; ++i)
        {
            for(int j = 1; j + y - 1 <= n; ++j)
            {
                ans = max(ans, sum[i + x - 1][j + y - 1] - sum[i + x - 1][j - 1] - sum[i - 1][j + y - 1] + sum[i - 1][j - 1]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}