BOJ 21321 - 클레이 사격 게임

BOJ 21321 - 클레이 사격 게임

비트마스크 + BFS 문제이다.

$i < j$ 이고 $a_i \mid a_j$ 라면 $a_j$ 는 $a_i$ 가 선행되어야 무조건 점수를 얻을 수 있다.

클레이를 사용한 상태를 $O(2^n)$ 개로 관리하며 DP로 각 상태에 대해 최대 점수를 관리해주면 된다.

void solve() {
   int n;
   cin >> n;
   vector<pi> a(n);
   for (auto &[a, b]: a) cin >> a >> b;
   vi blocked_by(n);

   for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
         if (a[j].fi % a[i].fi == 0) {
            blocked_by[j] |= (1 << i);
         }
      }
   }
   vi dp(1 << n);
   queue<int> q;
   q.push(0);
   while (sz(q)) {
      int bit = q.front();
      int cnt = __builtin_popcount(bit);
      q.pop();
      for (int i = 0; i < n; i++) {
         if (!(bit & (1 << i)) && (blocked_by[i] & bit) == blocked_by[i]) {
            int nxt = bit + (1 << i);
            if (dp[nxt] < dp[bit] + (cnt + 1) * a[i].se) {
               dp[nxt] = dp[bit] + (cnt + 1) * a[i].se;
               q.push(nxt);
            }
         }
      }
   }
   cout << dp[(1 << n) - 1];
}