HDU 1559 最大子矩阵 (DP) - c++编程基础

题目地址：HDU 1559

构造二维前缀和矩阵。即矩阵上的点a[i][j]表示左上方的点为(0,0)，右下方的点为(i,j)的矩阵的和。然后枚举每个矩阵的左上方的点，由于矩阵的长和宽是固定的，那么这个矩阵实际上也已经固定了。此时这个矩阵的和用公式：
sum=a[i+x-1][j+y-1]-a[i+x-1][j-1]-a[i-1][j+y-1]+a[i-1][j-1];

取最大值就可以了。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; #define LL __int64 LL a[1001][1001]; int main() { int t, n, m, i, j, k, x, y; LL z, max1; scanf("%d",&t); while(t--) { max1=-1; scanf("%d%d%d%d",&n,&m,&x,&y); memset(a,0,sizeof(a)); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%I64d",&z); a[i][j]=a[i][j-1]+z; } } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { a[i][j]+=a[i-1][j]; } } for(i=1;i<=n-x+1;i++) { for(j=1;j<=m-y+1;j++) { z=a[i+x-1][j+y-1]-a[i+x-1][j-1]-a[i-1][j+y-1]+a[i-1][j-1]; if(max1