HDU1081 （最大连续子序列/矩阵）

将二维转化为一维。

第一个FOR循环用于枚举行，第二个和第三个FOR 用于求从当前行（J）开始的每一个矩阵方块和，从而得到ANS。

View Code

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn = 105;
 5 int a[ maxn ][ maxn ],temp[ maxn ];
 6 int n;
 7 
 8 int dp( ){
 9     int ans=temp[ 0 ];
10     int tmp_sum=0;
11     for( int i=0;i<n;i++ ){
12         tmp_sum+=temp[ i ];
13         if( ans<tmp_sum ) ans=tmp_sum;
14         if( tmp_sum<0 ) tmp_sum=0;
15     }
16     return ans;
17 }
18 
19 int main(){
20     while( scanf("%d",&n)!=EOF ){
21         for( int i=0;i<n;i++)
22             for( int j=0;j<n;j++ )
23                 scanf("%d",&a[ i ][ j ]);
24         int ans=-9999999;
25         for( int i=0;i<n;i++ ){
26             memset( temp,0,sizeof(temp) );
27             for( int j=i;j<n;j++ ){
28                 for( int k=0;k<n;k++ ){
29                     temp[ k ]+=a[ j ][ k ];
30                 }
31                 ans=max( ans,dp() );
32             }
33         }
34         printf("%d\n",ans);
35     }
36     return 0;
37 }

keep moving...