Sicily 1563. GECKO

1333 단어
제목 배경은 재미있지만, 물문제예요...
한쪽 벽에는 많은 칸이 있고 칸마다 모기가 많으며 벽호 한 마리는 가능한 한 많은 모기를 먹고 싶어 한다.
그것의 법정 이동 방법은 그림과 같이 매우 2B이다.
모기를 최대 몇 마리까지 먹을 수 있는지 물어봐 주세요.
동적 기획은 해결할 수 있고 칸마다 최대 dp[i][j]마리의 모기를 먹을 수 있다.
그럼 이 값은 위 줄의 근접 칸에서만 얻을 수 있으며 후효성이 없습니다. dp.
코드:
#include <cstdio>
#include <iostream>
#include <memory.h>
using namespace std ;
#define maxn 509

int t,n;

int dp[maxn][maxn] ;
int a  ;

int main () {
    int h,w ;
    scanf ( "%d %d" , &h , &w ) ;
    for ( int j = 0 ; j < w ; ++j ) scanf ( "%d" , &dp[0][j] ) ;
    for ( int i = 1 ; i < h ; ++i ) 
        for ( int j = 0 ; j < w ; ++j ) {
            if ( j > 0 && j < w-1 ) 
                dp[i][j] = max ( max ( dp[i-1][j-1] , dp[i-1][j+1] ) , dp[i-1][j] ) ;
            else if ( j == 0 ) 
                dp[i][j] = max ( dp[i-1][j] , dp[i-1][j+1] ) ;
            else if ( j == w-1 ) 
                dp[i][j] = max ( dp[i-1][j-1] , dp[i-1][j] ) ;
                
            scanf ( "%d" , &a ) ;
            dp[i][j] += a ;
        }
    
    
    int ans = 0 ;
    for ( int j = 0 ; j < w ; ++j ) 
        ans = max  ( ans , dp[h-1][j] ) ;
    printf ( "%d
" , ans ) ; //system ( "pause" ) ; return 0 ; }

좋은 웹페이지 즐겨찾기