LHPC 2016 pC. 跳格子 ( DP )

沒有什麼玄機的 DP，注意要 long long。

void solve(){
    int N, M; cin >> N >> M;
    vvi C( 3, vi( 3 ) );
    for( int i = 0; i < 3; ++i )
        for( int j = 0; j < 3; ++j )
            cin >> C[ i ][ j ];
    vvi G( N, vi( M ) );
    vvl dp( N, vl( M ) );
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < M; ++j )
            cin >> G[ i ][ j ];
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < M; ++j ){
            if( j + 1 < M )
                upmax( dp[ i ][ j + 1 ], dp[ i ][ j ] + C[ G[ i ][ j ] ][ G[ i ][ j + 1 ] ] );
            if( i + 1 < N )
                upmax( dp[ i + 1 ][ j ], dp[ i ][ j ] + C[ G[ i ][ j ] ][ G[ i + 1 ][ j ] ] );
            if( i + 1 < N and j + 1 < M )
                upmax( dp[ i + 1 ][ j + 1 ], dp[ i ][ j ] + C[ G[ i ][ j ] ][ G[ i + 1 ][ j + 1 ] ] );
        }
    cout << dp[ N - 1 ][ M - 1 ] << endl;
}