Codeforces Round #222 (Div. 1) C. Captains Mode
このこどふぉ, なんとなく DDPC 本戦が想起される(B が priority_queue を使ったほげで, C が高速化出来る dp)
解法
pick するなら, 残っているもののうち一番でかいのを取ってくるのが最適です。
これを考えると, pick されるものとして考えるべきものは, 上位 m 個のみであるとわかります。
そこで, まず dp[turn][state] = (turn 目で, まだ pick も ban もされていない上位 m 人の状態が state である時の最適値)
という dp が考えられます。遷移では, turn 目で誰を pick/ban するかが m 通りあるので, 計算量は O(m^2 2^m) です。
C++ だとこれでも通りそうですが, ban する人はバラバラであると考えても良いこと, そう考えると turn は state のうち bit がたっているものの数で与えられることを考慮すると, dp[state] という状態だけで遷移ができるので, 計算量は O(m 2^m) です。
const int INF = 1e9; int n, m; int s[111], team[22]; int dp[1<<20]; char action[22]; int dfs(int state) { int& ret = dp[state]; if (ret > -INF) return ret; int turn = __builtin_popcount(state); if (turn == m) return ret = 0; if (team[turn] == 1) { ret = -INF/2; if (action[turn] == 'p') { for (int i = 0; i < m; i++) { if ((state>>i&1) == 0) { ret = max(ret, s[i]+dfs(state|(1<<i))); break; } } } else { for (int i = 0; i < m; i++) { if ((state>>i&1) == 0) { ret = max(ret, dfs(state|(1<<i))); } } } } else { ret = INF/2; if (action[turn] == 'p') { for (int i = 0; i < m; i++) { if ((state>>i&1) == 0) { ret = min(ret, -s[i]+dfs(state|(1<<i))); break; } } } else { for (int i = 0; i < m; i++) { if ((state>>i&1) == 0) { ret = min(ret, dfs(state|(1<<i))); } } } } return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n; for (int i = 0; i < n; i++) cin >> s[i]; sort(s, s+n); reverse(s, s+n); cin >> m; for (int i = 0; i < m; i++) { cin >> action[i] >> team[i]; } for (int i = 0; i < (1<<m); i++) dp[i] = -INF; cout << dfs(0) << endl; return 0; }