topcoder SRM366 Div2 Hard PickGuitars

問題URL : https://community.topcoder.com/stat?c=problem_statement&pm=8177&rd=10781

問題概要

n個のギターケースが円状に置かれている．
各ギターケースには価値G[i]のギターが入っている．
プレイヤーA,Bが交互にギターを取っていくゲームを行う．
ゲームのルールは以下の通りである．
空でない連続して並んでいるギターケースのグループについて，
プレイヤーAは各グループから１つずつギターケースを選びギターを取る．
次は，同じようにプレイヤーBが各グループからギターを取る．
以上の操作をギターがなくなるまで交互に繰り返す．
お互いのプレイヤーが取ったギターの価値の総和を最大にするように行動したとき，
プレイヤーAが取るギターの価値の総和を求めよ．

解法

よくある区間DP．
円状になっているが，プレイヤーAがギターを１つ選んでしまえば一列に並べて考えられる．
区間DPだと分かってしまえばあとは一瞬．

コード

vint v;
int n;

int dp[55][55];

int f(int l, int r, bool first=false){
    (l+=n)%=n;
    (r+=n)%=n;
    if(l==r) return v[l];
    if(dp[l][r]>=0) return dp[l][r];
    if(l>r) r+=n;
    int ret = -INF;
    int sum = 0;
    reep(i,l,r+1){
        sum += v[i];
    }
    if(first){
        reep(i,l,r+1){
            maxs(ret, sum-f(i+1, i-1));
        }
    }
    else{
        reep(i,l,r+1){
            if(i==l){
                maxs(ret, sum-f(l+1, r));
            }
            else if(i==r){
                maxs(ret, sum-f(l, r-1));
            }
            else{
                maxs(ret, sum-f(l, i-1)-f(i+1, r));
            }
        }
    }
    return dp[l%n][r%n] = ret;
}


struct PickGuitars {
    vector<int> g;
    int maxValue(vector<int> _guitarValues) {
        g = _guitarValues;
        n = g.size();
        v = vint(2*n);
        rep(i,n){
            rep(j,n){
                dp[i][j] = -1;
            }
        }
        rep(i,n){
            v[i] = g[i];
            v[i+n] = g[i];
        }        
        return f(0,n-1,true);
    }
};

コメント

典型でした