hdu 1081 To The Max - c++编程基础

给一个n^2矩阵求一个和最大的子矩阵

先预处理行或者列的和然后很好的转化成一维dp

这里我的 mp[i][j] 表示i行前j个数的和

dp的过程就是枚举列的首尾

这样相当于把每一行当成一个数 dp求最大和就是一个简单的问题了

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #define inf 0x3f3f3f3f #define ll __int64 int mp[105][105]; int main() { int n,a,i,j,k,tmp,ans; while(~scanf("%d",&n)) { memset(mp,0,sizeof mp); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&a); mp[i][j]=(a+mp[i][j-1]); } ans=-99999999; for(i=1;i<=n;i++)//起始列 { for(j=i;j<=n;j++)//结束列 { for(tmp=0,k=1;k<=n;k++)//枚举高度 { if(tmp<0) tmp=0; tmp+=(mp[k][j]-mp[k][i-1]); if(tmp>ans) ans=tmp; } } } printf("%d\n",ans); } return 0; }