AtCoder Regular Contest 056 C - 部門分け
うーん, 80 点はほしかったかも。
解法
bitDP します。
dp[state] = (state にあるものをうまく使ったときの最大スコア) とします。このとき, dp の更新は, state から適当な集団(state2 とする)を取り出して, 集合を state2 と state^state2 に分けたとき, state2 はこれからまださらに分割するとして, state^state2 はもう一つのグループとして確定させます。このときグループが一つ増えているので, スコアとしては K 増えますが, state2 と state^state2 に分けたことで減る分も考慮しないといけません。そこで,
dp[state] = max(K+dp[state2]-(state2 と state^state2 で減る分))
という漸化式が立ちます。この漸化式で問題なのは,
- state から state2 を列挙するのを高速でやらないといけない
- 二つの部分集合でかかるコストを高速で計算しないといけない
の 2 点です。
前者は, 結構いろんなところで出ている 4^n を 3^n にするテクニックです。例えばこんなところ
mayokoex.hatenablog.com
蟻本の 144p に書いてあるやつです。
後者は, memo[s] = (集合 s 内における信頼度の総和) というのを定義しておく(定義するのは遅くても O(2^n * n^2) とかでできる)と, (集合 s1 と集合 s2 の間の信頼度の総和) は memo[s1|s2] - memo[s1] - memo[s2] とすれば O(1) で計算できます。
後者全然気づかなかったし頭良い。
const int MAXN = 18; const ll INF = 1ll<<55; ll W[MAXN][MAXN]; ll memo[1<<MAXN]; ll dp[1<<MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; ll K; cin >> N >> K; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { cin >> W[i][j]; } for (int s = 0; s < 1<<N; s++) { for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) { int si = ((s>>i)&1); int sj = ((s>>j)&1); if (si & sj) { memo[s] += W[i][j]; } } } for (int state = 0; state < 1<<N; state++) { int sub = state; do { if (sub != 0) { dp[state] = max(dp[state], K+dp[state^sub]-memo[state]+memo[sub]+memo[state^sub]); } sub = (sub-1)&state; } while (sub != state); } cout << dp[(1<<N)-1] << endl; return 0; }