Grouping [Educational DP Contest / DP まとめコンテスト U]

https://atcoder.jp/contests/dp/tasks/dp_u

前提知識

• O(3^N)でのbitDP

解説

https://atcoder.jp/contests/dp/submissions/3949705

制約からbitDP感がある。
dp[msk] := グループが決まったうさぎがmskである場合の点数の最大値
dp[msk]を確定させたいときに、mskの部分集合msk2を列挙する方法がある。
msk2 ⊂ mskとすると、dp[msk] = dp[msk - msk2] + msk2のグループを作る事による点数
つまり、もともとmsk-msk2がグループが決まっているときに、msk2グループを作ることを行う。
この、bitDPで各状態について部分集合について更新を行うやり方はO(3^N)で行う方法がある。
　
3^16が4*10^7くらいあるので、「msk2のグループを作る事による得点」はO(1)くらいで求めたい。
なので、この得点は事前計算しておこう。
cst[msk] := mskのうさぎでグループを作るときの点数
各状態について全てのペアでコストを計算して足し合わせればいい。

int N, A[16][16];
ll dp[1 << 16];
ll cst[1 << 16];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) rep(j, 0, N) cin >> A[i][j];
 
    rep(msk, 0, 1 << N) {
        rep(i, 0, N) rep(j, i + 1, N) if (msk & (1 << i)) if (msk & (1 << j)) cst[msk] += A[i][j];
    }
 
    rep(msk, 0, 1 << N) {
        for (int msk2 = msk; msk2 > 0; msk2 = (msk2 - 1)&msk) {
            ll nxt = dp[msk - msk2] + cst[msk2];
            chmax(dp[msk], nxt);
        }
    }
 
    cout << dp[(1 << N) - 1] << endl;
}