ペアでチームを作ろう [yukicoder No.698]

https://yukicoder.me/problems/no/698

前提知識

• bitDP

解説

https://yukicoder.me/submissions/264246

bitDP感が出ているので、bitDP方針で考えてみる。
dp[msk] := 集合mskの人がペアになっている場合のスコアの最大値
として、遷移はペアを作るようにして全ての遷移を試す。
bitDPがわかっていると瞬殺。

int N, A[14], dp[1<<14];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    rep(msk, 0, 1 << N) {
        rep(a, 0, N) rep(b, a+1, N) if(!(msk & (1<< a))) if(!(msk & (1 << b))) {
            chmax(dp[msk + (1 << a) + (1 << b)], dp[msk] + (A[a] ^ A[b]));
        }
    }
    cout << dp[(1 << N) - 1] << endl;
}