1245aaa.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include <iostream> 
#include <fstream> 
#include <string> 
using namespace std ; 
const int MaxNum=110;
int num[ MaxNum ][ 2*MaxNum+1 ]; 
char table[ MaxNum ][ 2*MaxNum+1 ]; 
int n; 
void Init() 
{ 
   int i,j; 
   for( i=0 ; i<n ; i++ ) 
   { 
      num[ i ][ 0 ] = ( table[ i ][ 0 ] == '-' ? 1 : 0 ) ; 
      for( j=1 ; j<2*(n-i)-1; j++ ) 
      { 
         if ( table[ i ][ j ] == '-' ) num[ i ][ j ] = num[ i ][ j-1 ] + 1; 
         else num[ i ][ j ] = 0; 
       } 
   } 
} 
int getArea( int y , int x , int len , int dir ) 
{ 
   int result = 0 ; 
   while( y >= 0 && x >= 0 && y < n && x < ( n - y )*2-1 && num[ y ][ x ] >= len ) 
   { 
      result += len; 
      y+=dir ; 
        x+=(dir==-1?2:0); 
       len+=2; 
   } 
   return result; 
} 
int main() 
{  ifstream from ( "1245.txt" ) ; 
   int i, j; 
   int MaxArea ; 
   int tmp; 
   int nCase = 1; 
   while( from >> n && n ) 
   { 
        cout << "Triangle #" << nCase++ << endl; 
        for( i=0 ; i<n ; i++ ) 
           from >> table[ i ];  
        Init(); 
        MaxArea = 0 ; 
        for( i=0 ; i<n ; i++ ) 
        { 
           for( j=0 ; j<2*(n-i)-1 ; j++ ) 
           { 
              if ( table[ i ][ j ] == '#' ) 
               { 
                  continue; 
               } 
              if ( j % 2 ) 
               { 
                  tmp = getArea( i , j , 1 , 1 ); 
                  if ( tmp > MaxArea ) MaxArea = tmp; 
               } else 
               { 
                    tmp = getArea( i , j , 1 , -1 ); 
                 if ( tmp > MaxArea ) MaxArea = tmp; 
              } 
           } 
       } 
      cout << "The largest triangle area is " << MaxArea << "." << endl << endl; 
   } 
    
     return 0; 
}