UVA 10891 Game of Sum ( DP )

UVa Online Judge
最佳策略其實就是留給對手最差的狀態，從這部份著手，很容易得到轉移方程：
dp( i, j ) = sum( i, j ) - min{ 0, min{ dp( k, j ), dp( i, k ) | Ɐ i ≤ k ≤ j } }
用言語表達就是要嘛左邊取來要嘛右邊取來，甚至是全取( 留 0給對手 )會讓對手有最少得分。樸素的寫出來就是個 2D / 1D算法。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 10;

int kase;
int _s[MAXN], G[MAXN];
int sum(int i, int j){ return _s[j] - _s[i - 1]; }

int memo[MAXN][MAXN], vis[MAXN][MAXN];
int dp(int l, int r){
    if( vis[l][r] == kase ) return memo[l][r];
    vis[l][r] = kase;
    int &ans = memo[l][r]; ans = 0;
    int m = 0;
    for(int i = l + 1; i <= r; ++i) m = min( m, dp( i, r ) );
    for(int i = l; i < r; ++i) m = min( m, dp( l, i ) );
    ans = sum( l, r ) - m;
    return ans;
}

int main(){
    int n;
    while( scanf("%d", &n) == 1 && n ){
        ++kase;
        for(int i = 1; i <= n; ++i){
            scanf("%d", &G[i]);
            _s[i] = _s[i - 1] + G[i];
        }
        printf("%d\n", dp( 1, n ) - ( sum( 1, n ) - dp( 1, n ) ));
    }
    return 0;
}

但其實可以壓低轉移的複雜度，如果我們用 tl[ i ][ j ]表示 min{ dp[ i ][ j ], dp[ i + 1 ][ j ] .., dp[ j ][ j ] }, tr[ i ][ j ]表示 min{ dp[ i ][ j ], dp[ i ][ j - 1 ] .., dp[ i ][ i ] }，我們可以將前面的方程式改寫成
dp[ i ][ j ] = sum( i, j ) - min{ 0, tl[ i + 1 ][ j ], tr[ i ][ j - 1 ] }
也就是可以 O( 1 ) 知道從左拿可以留給對方怎樣最差的，亦知從右拿可以留給對方怎樣最差的。維護這兩樣東西不難，但要改成依據區間長度更新。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 2;

int n;
int a[MAXN], pa[MAXN];

int dp[MAXN][MAXN];
int tl[MAXN][MAXN], tr[MAXN][MAXN];
void solve(){
    memset( dp, -1, sizeof(dp) );
    for(int i = 1; i <= n; ++i)
        dp[i][i] = tl[i][i] = tr[i][i] = a[i];
    for(int len = 2; len <= n; ++len){
        for(int i = 1; i <= n; ++i){
            int j = i + len - 1; // [ i, i + len ) = [ i, j ]
            int nxt = min( tl[i + 1][j], tr[i][j - 1] );
            nxt = min( nxt, 0 );
            dp[i][j] = pa[j] - pa[i - 1] - nxt;
            tl[i][j] = min( dp[i][j], tl[i + 1][j] );
            tr[i][j] = min( dp[i][j], tr[i][j - 1] );
        }
    }
    printf("%d\n", 2 * dp[ 1 ][ n ] - pa[ n ]);
}

int main(){
    while( scanf("%d", &n) == 1 && n ){
        for(int i = 1; i <= n; ++i){
            scanf("%d", &a[i]);
            pa[ i ] = pa[ i - 1 ] + a[ i ];
        }
        solve();
    }
    return 0;
}