poj1050To the Max解题报告<DP>

题意:求给定的矩阵的最大子矩阵和;

思路:将二维转化为一维求最大连续子串和;母串为从原矩阵中截取连续的几行,求其最大子串和;

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string>
 4 #include <cstring>
 5 #include <cmath>
 6 using namespace std;
 7 
 8 int N, a[105][105], s[105];
 9 
10 int main( )
11 {
12     while( scanf( "%d", &N )!= EOF ){
13         for( int i=0; i<N; ++ i ){
14             for( int j=0; j<N; ++ j){
15                 scanf( "%d", &a[i][j] );
16             }
17         }
18         int ans=-(1<<30);
19         for( int i=0; i<N; ++ i ){              //开始行 
20             memset( s, 0, sizeof s );
21             for( int j=i; j<N; ++j ){         //结束行 
22                 for( int k=0; k<N; ++ k ){  //把一列作为 整体看成一个元素 
23                     s[k]+=a[j][k];
24                 }
25                 int temp=-(1<<30), b=s[0];
26                 for(int t=1;t<N; ++ t ){   //求最大连续子串 
27                     if( b<0 )b=s[t];
28                     else b+=s[t];
29                     if( temp<b )temp=b;
30                 }
31                 ans=ans>temp?ans:temp;
32             }
33         }
34         printf( "%d\n", ans );
35         
36     }    
37     return 0;
38 }