Codeforces 377(#222 Div1) C. Captains Mode

問題

n個の石を二人が取り合う。i番目の石の得点はa[i]点。

二人が取れる行動は予め決まっていて、第iターン目には、
プレイヤーt[i]が、
s[i] = 'b'なら場の石を一個捨てる（両プレイヤーに点数は入らない）、
s[i] = 'p'なら場の石を自分のものにする（自分にa[i]点が入る）

両者が最善を尽くして石を選ぶとき、先手の得点 - 後手の得点の最大値を求めよ。

制約条件

n≦100
m≦min(n, 20)

方針

得点が大きい順にm個の石だけが関係するので、その石だけ考える。
すると石は20個になるのでmin-maxがbitDPできる。

ソースコード

int n, a[100], m, t[20];
char in[20];

int dp[1 << 20];
int rec(int mask, int c){
	int &res = dp[mask];
	
	if(res < inf) return res;
	if(c == m)    return res = 0;
	if(t[c] == 1) res = -inf;
	
	rep(i, m) if(!(mask & 1 << i)){
		
		if(t[c] == 1) res = max(res, rec(mask ^ 1 << i, c + 1) + (in[c] == 'b' ? 0 : a[i]));
		if(t[c] == 2) res = min(res, rec(mask ^ 1 << i, c + 1) - (in[c] == 'b' ? 0 : a[i]));
	}
	return res;
}

int main(){
	rep(i, 1 << 20) dp[i] = inf;
	
	cin >> n;
	rep(i, n) cin >> a[i];
	cin >> m;
	rep(i, m) cin >> in[i] >> t[i];
	sort(a, a + n, greater<int>());
	
	cout << rec(0, 0) << endl;
	
	return 0;
}