HDU 1559 最大子矩阵和 二维前缀和

//二维前缀和
#include<iostream>
#include<algorithm>
using namespace std;

int t, n, m;
int x, y;
int matrix[1001][1001];
int dp[1001][1001];

int main()
{    
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d %d %d", &n, &m, &x, &y);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                scanf("%d", &matrix[i][j]);
        //预处理
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+matrix[i][j];

        int ans = 0;
        //(i-x+1, j-y+1) (i, j)
        for(int i = x; i <= n; i++)
            for(int j = y; j <= m; j++)
                ans = max(ans, dp[i][j]-dp[i-x][j]-dp[i][j-y]+dp[i-x][j-x]);
        cout << ans << endl;
    }
    //system("pause");
    return 0;
}

HDU 1559 最大子矩阵和 二维前缀和

原文：https://www.cnblogs.com/znk97/p/14290461.html