問題概要
$N$羽のうさぎをいくつかのグループに分けたい.
うさぎ$i$とうさぎ$j$の相性は$a_{i, j}$である.
各グループのスコアを, そのグループに属する任意の2羽のうさぎの相性の和とする.
スコアの最大値を求めなさい.
制約
- $1 \leq N \leq 16$
- $a_{i, i} = 0$
- $|a_{i, j}| \leq 10^9$
- $a_{i, j} = a_{j, i}$
考察
制約がbitDPだと言っているので従う.
DPの定義を考える. 「$dp[msk] := msk$を分けるときの答え」とすると, 求めるべきは$dp[(1 << N) - 1]$となる.
$msk$の$popcount$が$1$なら自明に$dp[msk] = 0$.
そうじゃないなら, $\displaystyle dp[msk] = \max_{y \subseteq msk} ( dp[y] + dp[y\ \mathrm{XOR}\ msk] )$のように部分集合を列挙すればよい.
愚直に部分集合を列挙すると$O(4^N)$だけど, いい感じにすると$O(3^N)$に落ちる(参考).
提出コード(C++🔆)
int N;
vector<vector<int>> A;
vector<ll> memo;
ll calc(int msk) {
if (memo[msk] != -INFF) return memo[msk];
ll ret = 0;
REP(i, N) if (msk & (1 << i)) REP(j, i, N) if (msk & (1 << j)) ret += A[i][j];
return memo[msk] = ret;
}
vector<bool> visited;
vector<ll> dp;
ll rec(int msk) {
if (visited[msk]) return dp[msk];
visited[msk] = true;
if (__builtin_popcount(msk) == 1) return dp[msk] = 0;
ll ret = calc(msk);
for (int y = 0; ; y = (y - msk) & msk) { // 参考
if (y == msk) break;
int y_rev = msk ^ y;
chmax(ret, rec(y) + rec(y_rev));
}
return dp[msk] = ret;
}
signed main() {
cin >> N;
A = make_v<int>(N, N);
REP(i, N) REP(j, N) cin >> A[i][j];
memo.assign(1 << N, -INFF);
visited.assign(1 << N, false);
dp.assign(1 << N, -INFF);
cout << rec((1 << N) - 1) << endl;
}