hdu1081-To The Max

DP,最大矩陣和，首先將橫坐標的數值，分別求和存儲在二維數組中，然後使用三個for循環，第一二層分別表示第I 橫層 ，和第j 橫層，然後做差，就求出了縱坐標的和，當sum〉0就由k 向右累加；

[cpp]
#include<iostream>  
#include<cstdio>  
#include<cstring>  
 
using namespace std ; 
 
int dp[ 150 ][ 150 ] ; 
 
int main() 
{ 
    int n ; 
    int i , j , k , t , maxn ; 
    while( ~scanf( "%d" , &n ) ) 
    { 
        memset( dp , 0 , sizeof( dp ) ); 
        for( i = 0 ; i < n ; ++i ) 
            for( j = 0 ; j < n ; ++j ) 
            { 
                scanf( "%d" , &t ) ; 
                dp[ i ][ j ] = dp[ i - 1 ][ j ] + t ; 
            } 
            maxn = -1 ; 
            for( i = 0 ; i < n ; ++i ) 
                for( j = i ; j < n ; ++j ) 
                { 
                    int sum = 0 ; 
                    for( k = 0 ; k < n ; ++k ) 
                    { 
                        t = dp[ j ][ k ] - dp[ i - 1 ][ k ] ;  
                        sum += t ; 
                        if( sum < 0 ) 
                            sum = 0 ; 
                        if ( sum > maxn ) 
                            maxn = sum ; 
                    } 
                } 
                printf( "%d\n" , maxn ) ; 
    } 
    return 0 ; 
} 

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std ;

int dp[ 150 ][ 150 ] ;

int main()
{
 int n ;
 int i , j , k , t , maxn ;
 while( ~scanf( "%d" , &n ) )
 {
  memset( dp , 0 , sizeof( dp ) );
  for( i = 0 ; i < n ; ++i )
   for( j = 0 ; j < n ; ++j )
   {
    scanf( "%d" , &t ) ;
    dp[ i ][ j ] = dp[ i - 1 ][ j ] + t ;
   }
   maxn = -1 ;
   for( i = 0 ; i < n ; ++i )
    for( j = i ; j < n ; ++j )
    {
     int sum = 0 ;
     for( k = 0 ; k < n ; ++k )
     {
      t = dp[ j ][ k ] - dp[ i - 1 ][ k ] ;
      sum += t ;
      if( sum < 0 )
       sum = 0 ;
      if ( sum > maxn )
       maxn = sum ;
     }
    }
    printf( "%d\n" , maxn ) ;
 }
 return 0 ;
}