HDU 1559 最大子矩阵

Description

给你一个m×n的整数矩阵，在上面找一个x×y的子矩阵，使子矩阵中所有元素的和最大。

Input

输入数据的第一行为一个正整数T，表示有T组测试数据。每一组测试数据的第一行为四个正整数m,n,x,y（0<m,n<1000 AND 0<x<=m AND 0<y<=n），表示给定的矩形有m行n列。接下来这个矩阵，有m行，每行有n个不大于1000的正整数。

Output

对于每组数据，输出一个整数，表示子矩阵的最大和。

Sample Input

1

4 5 2 2

3 361 649 676 588

992 762 156 993 169

662 34 638 89 543

525 165 254 809 280

Sample Output

2474

思路

int a[i][j]存读入的数值，int sum[i][j]计算二维前缀和（从左上角顶点到点（i, j）所形成矩阵的和)，动态规划求最值。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int a[1005][1005];
int sum[1005][1005];

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int m, n, x, y;
        cin >> m >> n >> x >> y;

        ///数据存储
        for(int i = 1; i <= m; ++i)
            for(int j = 1; j <= n; ++j)
            cin >> a[i][j];

        ///二维前缀和计算
        for(int i = 1; i <= m; ++i)
            for(int j = 1; j <= n; ++j)
            sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];

        ///动态规划
        int ans = 0;/// 初始化为 <= 0的任何数都行
        for(int i = x; i <= m; ++i)
            for(int j = y; j <= n; ++j)
            ans = max(ans, sum[i][j] - sum[i - x][j] - sum[i][j - y] + sum[i - x][j - y]);

        cout << ans << '\n';
        memset(a, 0, sizeof(a));
        memset(sum, 0, sizeof(sum));
    }
    return 0;
}