hdu 1559 最大子矩阵

大略看了题意以后，觉得与HDU 1081 To The Max 类似，求最大子矩阵之和。但有不同之处。这里求矩阵为 x*y的最大和。dp没有想法，就按那个题的思路敲，最后直接成暴力了,2000ms+。后来瞄了别人的dp,发现dp几行就搞定,又用dp300ms+过了。

dp[i][j] 表示 （1,1）~（i,j）的和。当 i >= x && j >= y 时，以它为右下角的x*y的矩阵和为dp[i][j]-dp[i-x][j]-dp[i][j-y]+dp[i-x][j-y]，最后求出最大的。

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int dp[1510][1510]; int main() { int test; int n,m,x,y; scanf(%d,&test); while(test--) { memset(dp,0,sizeof(dp)); scanf(%d %d %d %d,&n,&m,&x,&y); int ans = -1; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { scanf(%d,&dp[i][j]); dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]; if(i >= x && j >= y) { int tmp = dp[i][j]-dp[i-x][j]-dp[i][j-y]+dp[i-x][j-y]; ans = max(ans,tmp); } } } printf(%d ,ans); } return 0; } 
    
   
  

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int sum[2010][2010]; int a[2010][2010]; int main() { int n,m,x,y; int test; scanf(%d,&test); while(test--) { 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,&a[i][j]); memset(sum,0,sizeof(sum)); for(int j = 1; j <= m; j++) { for(int i = 1; i <= n+x-1; i++) { for(int k = i; k <= i+x-1; k++) { sum[i][j] += a[k][j]; } } }
    
   
  

        int s;
        int ans = -1;
        for(int i = 1; i <= n+1-x; i++)
        {
            s = 0;
            for(int j = 1; j <= y; j++)
                s += sum[i][j];

            int maxn = s;
            for(int j = y+1; j <= m; j++)
            {
              s = s-sum[i][j-y] + sum[i][j];
               maxn = max(maxn,s);
            }
            ans = max(ans,maxn);
        }
       printf(%d
,ans);
    }
    return 0;
}