読者です 読者をやめる 読者になる 読者になる

topcoder SRM366 Div2 Hard PickGuitars

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

{ \displaystyle
}

問題概要

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

解法

よくある区間DP.
円状になっているが,プレイヤーAがギターを1つ選んでしまえば一列に並べて考えられる.
区間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);
    }
};

コメント

典型でした