2738:Two Ends

keyword

動的計画法　C++

概要

N(<1000)個の数列が与えられる。プレイヤー二人は交互に数列の両端どちらかの数字をとる。取った数字の合計値がスコアになる。後手の戦略が貪欲法であるとき、先手は後手よりどれだけ高いスコアをとれるか求める問題。
dp[iターンまで終了][残っている数列の左はどこか]でDPする。最後の処理に引っかかった。

static int ns[1001];
static int dp[1001][1002];

int main(){
    int cnt=0, i, j, n;
    while(n = readint(), n){
        REP(i,n)REP(j,n+1) dp[i][j] = -(1<<30);
        REP(i,n) ns[i] = readint();
        dp[0][0] = 0;
        REP(i,(n>>1)){
            REP(j,n)if(dp[i][j] > -(1<<30)){
                int l = j, r = j + (n-2*i) - 1;

                if(ns[l+1] < ns[r])
                    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+ns[l]-ns[r]);
                else
                    dp[i+1][j+2] = max(dp[i+1][j+2], dp[i][j]+ns[l]-ns[l+1]);

                if(ns[l] < ns[r-1])
                    dp[i+1][j] = max(dp[i+1][j], dp[i][j]+ns[r]-ns[r-1]);
                else
                    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+ns[r]-ns[l]);
            }
        }
        int ans = -(1<<30);
        REP(i,n+1) ans = max(ans, dp[n>>1][i]);

        printf("In game %d, the greedy strategy might lose by as many as %d points.\n",++cnt, ans);
    }
    return 0;
}