SRM694 Div1 Easy "TrySail"
解法
dpる。
まず全員をteam1に加入させておく。
それから、生徒ごとに着目していき、team2及びteam3に移籍させる場合を考えていく。
team2及びteam3それぞれのチーム力とすることが可能かどうか記録しておき、それを更新していく。
dp[team2/team3それぞれのチーム力] := それが可能?
事後
255は0x11111111じゃない。。0b11111111だったよ。。orz
ソースコード
bool dp[2][1 << 16]; class TrySail { public: int get(vector<int> strength) { int n = strength.size(); // 全員チーム1に加入しとく int all = 0; for (int i = 0; i < n; i++) { all ^= strength[i]; } // dp初期化 for (int i = 0; i < 2; i++) { for (int b = 0; b < (1 << 16); b++) { dp[i][b] = false; } } int cur = 0; int next = 1; dp[cur][0] = true; // dp更新 for (int i = 0; i < n; i++) { // next初期化 for (int b = 0; b < (1 << 16); b++) { dp[next][b] = false; } // 加入していく for (int b = 0; b < (1 << 16); b++) { if (!dp[cur][b]) continue; // チーム1に残留 dp[next][b] = true; // チーム2に移籍 dp[next][b ^ strength[i]] = true; // チーム3に移籍 dp[next][b ^ (strength[i] << 8)] = true; } // cur next交代 cur = 1 - cur; next = 1 - next; } // 答え算出 int answer = 0; for (int b = 0; b < (1 << 16); b++) { if (!dp[cur][b]) continue; int t2 = b & 0b11111111; int t3 = (b >> 8) & 0b11111111; int t1 = all ^ t2 ^ t3; answer = max(answer, t1 + t2 + t3); } return answer; } };