IOI '96 A Game ( Easy DP )

PEG Judge - IOI '96 - A Game
經典問題 就不多說了。
好啦，dp[ i ][ j ] 就是 [ i, j ] 的情況下先手最高得分，轉移的時候使對手最小，min-max問題。

void subSolve( int ql, int qr, const vi &A, const vi &pA, vvi &dp ){
    if( dp[ ql ][ qr ] != -1 ) return;
    if( ql == qr ) return ( void )( dp[ ql ][ qr ] = A[ ql ] );
    subSolve( ql + 1, qr, A, pA, dp );
    subSolve( ql, qr - 1, A, pA, dp );
    if( dp[ ql + 1 ][ qr ] < dp[ ql ][ qr - 1 ] )
        dp[ ql ][ qr ] = pA[ qr + 1 ] - pA[ ql ] - dp[ ql + 1 ][ qr ];
    else
        dp[ ql ][ qr ] = pA[ qr + 1 ] - pA[ ql ] - dp[ ql ][ qr - 1 ];
}

void solve(){
    int N; cin >> N;

    vi A( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];

    vi pA( N + 1 );
    for( int i = 0; i < N; ++i )
        pA[ i + 1 ] = pA[ i ] + A[ i ];

    vvi dp( A.size(), vi ( A.size() ) );
    for( int i = 0; i < A.size(); ++i )
        for( int j = 0; j < A.size(); ++j )
            dp[ i ][ j ] = -1;

    subSolve( 0, A.size() - 1, A, pA, dp );

    cout << dp[ 0 ][ A.size() - 1 ] << " " <<  pA[ A.size() ] - dp[ 0 ][ A.size() - 1 ] << "\n";
}