HDU 1559最大サブマトリックス

/**
*   Author : johnsondu
*   time : 2013-4-7
*   Type: DP, I want to really understand it
*   problem:      
*   url: http://acm.hdu.edu.cn/showproblem.php?pid=1559
*/

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

#define MAXN 1005
int mat[MAXN][MAXN] ;
int n, m, sn, sm ;

int sum[MAXN][MAXN] ;

int main ()
{
    int tcase ;
    int i, j ;
    //freopen ("data.txt", "r", stdin) ;
    scanf ("%d", &tcase) ;
    while (tcase --)
    {
        scanf ("%d%d%d%d", &n, &m, &sn, &sm) ;
        for (i = 0; i < n; i ++)
            for (j = 0; j < m; j ++)
                scanf ("%d", &mat[i][j]) ;

        memset (sum, 0, sizeof (sum)) ;
        for (i = 0; i < n; i ++)        //    ，sum[0][1] = sum[0][0] + a[0][1] ;
        {
            sum[i][0] = mat[i][0] ;
            for (j = 1; j < m; j ++)
                sum[i][j] = sum[i][j-1] + mat[i][j];
        }
        for (i = 1; i < n; i ++)                //    ，        (r, c) (0, 0)      
            for (j = 0; j < m; j ++)
                sum[i][j] += sum[i-1][j] ;

        int res = sum[sn-1][sm-1] ;
        for (i = sn-1; i < n; i ++)             //  ：     mat[i-sn][j] - mat[i][j-sm],    
            for (j = sm-1; j < m; j ++)
            {
                if (i == sn-1 && j == sm-1)
                    continue ;
                if (i == sn-1)
                    res = max (res, sum[i][j] - sum[i][j-sm]) ;
                else if (j == sm-1)
                    res = max (res, sum[i][j] - sum[i-sn][j]) ;
                else res = max (res, sum[i][j]-sum[i-sm][j]-sum[i][j-sn] + sum[i-sn][j-sm]) ;
            }
        printf ("%d
", res) ;

    }
    return 0 ;
}