ARC056 C - 部門分け

問題ページ
C - 部門分け

考えたこと

• O(N!)すれば部分点40点ははい
• 部門数とか何か条件を決め打てばスコアが一意に定まるみたいなのを考える
• 部門数M = N からはじめてもっともスコアが上がる方法で M = N-1 につなぐ貪欲→明らかにだめなパターンが存在
• すでに同じ部門になってる社員のbitを1にしてbitDP→部門複数あるしbitで扱えなくない？
• すでにつないだやつをうまいこともって頑張れない？→O(N^N)にしかならないが
  -----解説を見た-----
• dp[S] = (頂点集合Sの解) としてDPをする
• 部分集合の部分集合はO(3^N)のため解ける

学び

• dp[S] = (頂点集合Sについて) みたいなDPの条件の取り方
• Sの部分集合Tのdp[T]から全列挙して遷移するようなのはO(3^N)

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int n, K;
int w[20][20];
int dp[1LL<<17], dp2[1LL<<17];

signed main(void)
{
  cin >> n >> K;
  REP(i, n) REP(j, n) cin >> w[i][j];
  // dp2[S] = (頂点集合Sの辺の重みの和)
  REP(i, 1<<n) {
    REP(j, n) FOR(k, j+1, n) {
      if((i&1<<j) && (i&1<<k)) {
        dp2[i] += w[j][k];
      }
    }
  }

  FOR(s, 1, 1<<n) {
    // 集合sの部分集合tを全列挙
    int t = s;
    do {
      // 差集合はs-tで求まる
      chmax(dp[s], dp[s-t] + K - (dp2[s] - dp2[s-t] - dp2[t]));
      t = (t-1) & s;
    } while(t != 0);
  }
  cout << dp[(1<<n)-1] << endl;

  return 0;
}