codeforces 429B B. Working out(dp)

제목 링크:

codeforces 429B

제목 대의:

한 사람이 왼쪽 상단에서 오른쪽 하단으로, 한 사람이 왼쪽 하단에서 오른쪽 상단으로 가면 두 사람은 한 점에서만 교차한다. 두 사람이 경로를 지나는 수와 가장 큰 상황에서 가장 큰 합이 얼마냐고 묻는다.

제목 분석:

4

각각 네 개의 각에서 출발하여 동적 기획을 할 수 있다. dp[k][i][j]는 첫 번째 k개의 각에서 출발하여 i와 j가 얻은 가장 큰 수를 대표한다

4

각 점을 매거한 다음에 매거가 네 개의 각에서 동시에 큰 점까지의 경우 왼쪽 상각이 왼쪽 또는 상측에서 오른쪽 하각이 오른쪽 또는 하측에서 다른 이치와 같다. 매거한 점만 교차하기 때문에 우리는 왼쪽 상각이 왼쪽에서 들어가면 왼쪽이 작아도 이 점에 도달해야 하기 때문에 오른쪽 하각의 점은 반드시 오른쪽에서 들어가야 한다고 볼 수 있다.같은 이치로 오른쪽 상각은 반드시 상측에서 들어가야 한다. 만약에 왼쪽 상각이 상측에서 들어가면 동리가 발견하면 처음에는 단지 하나의 상황만 있을 뿐이다

4

문제는 어렵지 않지만 세심하고 인내심 있게 써야 한다

AC 코드:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 1007

using namespace std;

int n,m;
int a[MAX][MAX];
int u,v;
int dp[4][MAX][MAX];

int main ( )
{
    while ( ~scanf ( "%d%d" , &n , &m ) )
    {
        for ( int i = 1 ; i <= n ; i++ )
            for ( int j = 1 ; j <= m ; j++ )
                scanf ( "%d" , &a[i][j] );
        for ( int i = 1 ; i <= n ; i++ )
            for ( int j = 1 ; j <= m ; j++ )
            {
                dp[0][i][j] = 0;
                if ( i > 1 ) 
                    dp[0][i][j] = max ( dp[0][i-1][j] , dp[0][i][j] );
                if ( j > 1 ) 
                    dp[0][i][j] = max ( dp[0][i][j-1] , dp[0][i][j] );
                dp[0][i][j] += a[i][j];
            }
        for ( int i = n ; i >= 1 ; i-- )
            for ( int j = 1 ; j <= m ; j++ )
            {
                dp[1][i][j] = 0;
                if ( i < n )
                    dp[1][i][j] = max ( dp[1][i+1][j] , dp[1][i][j] );
                if ( j > 1 )
                    dp[1][i][j] = max ( dp[1][i][j-1] , dp[1][i][j] );
                dp[1][i][j] += a[i][j];
            }
        for ( int i = 1 ; i <= n ; i++ )
            for ( int j = m ; j >= 1 ; j-- )
            {
                dp[2][i][j] = 0;
                if ( i > 1 )
                    dp[2][i][j] = max ( dp[2][i-1][j] , dp[2][i][j] );
                if ( j < m )
                    dp[2][i][j] = max ( dp[2][i][j+1] , dp[2][i][j] );
                dp[2][i][j] += a[i][j];
            } 
        for ( int i = n ; i >= 1 ; i-- )
            for ( int j = m ; j >= 1 ; j-- )
            {
                dp[3][i][j] = 0;
                if ( i < n )
                    dp[3][i][j] = max ( dp[3][i+1][j] , dp[3][i][j] );
                if ( j < m )
                    dp[3][i][j] = max ( dp[3][i][j+1] , dp[3][i][j] );
                dp[3][i][j] += a[i][j];
            }
        /*for ( int i = 1 ; i <= n ; i++ )
            for ( int j = 1 ; j <= m ; j++ )
            {
                dp[0][i][j+1] = max ( dp[0][i][j+1] , dp[0][i][j] + a[i][j+1] );
                dp[0][i+1][j] = max ( dp[0][i+1][j] , dp[0][i][j] + a[i+1][j] );
            }

        for ( int i = 1 ; i <= n ; i++ )
            for ( int j = m ; j >= 1; j-- )
            {
                dp[2][i][j-1] = max ( dp[2][i][j-1] , dp[2][i][j] + a[i][j-1] );
                dp[2][i+1][j] = max ( dp[2][i+1][j] , dp[2][i][j] + a[i+1][j] );
            }

        for ( int i = n ; i >= 1 ; i-- )
            for ( int j = 1 ; j <= m ; j++ )
            {
                dp[1][i][j+1] = max ( dp[1][i][j+1] , dp[1][i][j] + a[i][j+1] );
                dp[1][i-1][j] = max ( dp[1][i-1][j] , dp[1][i][j] + a[i-1][j] );
            }

        for ( int i = n ; i >= 1 ; i-- )
            for ( int j = n ; j >= 1 ; j-- )
            {
                dp[3][i][j-1] = max ( dp[3][i][j-1] , dp[3][i][j] + a[i][j-1] );
                dp[3][i-1][j] = max ( dp[3][i-1][j] , dp[3][i][j] + a[i-1][j] );
            }*/
        int ans = 0;
        for ( int i = 2; i < n ; i++ )
            for ( int j = 2; j < m ; j++ )
            {
                ans = max ( ans , dp[0][i-1][j]+dp[3][i+1][j]+dp[1][i][j-1]+dp[2][i][j+1] );
                ans = max ( ans , dp[0][i][j-1]+dp[3][i][j+1]+dp[1][i+1][j]+dp[2][i-1][j] );
            }
        printf ( "%d
" , ans );
    }
}