bitDPでの集めるDPと配るDPについて

こんなツイートが

このときは「わかる」ってなってたんですけど

いざ問題を解いてみるとそんなこと無いな,なんでだろう,みないな記事です

以下の問題のネタバレを含みます 気をつけてください

https://yukicoder.me/problems/no/357

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0263

考える問題1

https://yukicoder.me/problems/no/357















空白

集めるDP

で書くとこうなる

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int N,M;

i64 score[14][14];

i64 dp[1 << 14];
int main(){
  cin >> N >> M;
  for(int i = 0;i < M;i++){
    i64 a,b,c;
    cin >> a >> b >> c;
    score[a][b] = c;
  }

  for(int s = 1;s < (1 << N);s++){
    for(int p = 0;p < N;p++){
      int t = s & ~(1 << p);
      if(t == s) continue;
      i64 res = 0;
      for(int i = 0;i < N;i++){
        if(t & (1 << i)){
          res += score[i][p];
        }
      }
      dp[s] = max(dp[s],dp[t] + res);
    }
  }

  cout << dp[(1 << N) - 1] << endl;
}

集めるbitDPは

int t = s & ~(1 << p);

としてやることでp番のアイテムを置く前の状態を表現できる

このとき

if(t == s) continue;

とするのが重要で,置く前の状態になっているかを確認する

配るDP

で書くとこうなる

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int N,M;

i64 score[14][14];

i64 dp[1 << 14];
int main(){
  cin >> N >> M;
  for(int i = 0;i < M;i++){
    i64 a,b,c;
    cin >> a >> b >> c;
    score[a][b] = c;
  }

  for(int s = 0;s < (1 << N);s++){
    for(int p = 0;p < N;p++){
      int t = s | (1 << p);
      if(t == s) continue;
      i64 res = 0;
      for(int i = 0;i < N;i++){
        if(s & (1 << i)){
          res += score[i][p];
        }
      }
      dp[t] = max(dp[t],dp[s] + res);
    }
  }

  cout << dp[(1 << N) - 1] << endl;
}

配るbitDPは

int t = s | (1 << p);

としてやることでp番を置いたあとの状態を表現できる

if(t == s) continue;

も同様である

ここはあんまり差が無い

まあなんとかなるかなぁみたいな

本題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0263
















もち

遷移

i回目の点灯の前の状態をstateとします

するとi回目の点灯があったあとはstate | A[i]という状態になります

その後、プレイヤーがjのパターンでボタンを押すと(state | A[i]) & ~B[i]という状態になります

このとき押したボタンの数は(state | A[i]) & B[i]のビットの立っている数です

つまり遷移は

dp[i + 1][(s | A[i]) & ~(B[j])] = 
        max(dp[i + 1][(s | A[i]) & ~(B[j])] , 
            dp[i][s] + __builtin_popcount((s | A[i]) & B[j]));

これは配るDPですね

集めるDPは？

遷移が思いつきにくい

なんで？

ゲームはすすめるイメージが強いのかなぁ...

でもしっかり配るDPでできたし、こっちのほうが素直

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
 
int N;
int C;
vector<i64> A,B;
 
int dp[31][1 << 16];
 
int solve(){
 
  rep(i,0,30){
    rep(j,0,(1 << 16) - 1) dp[i][j] = -1e9;
  }
  dp[0][0] = 0;
  cin >> N >> C;
  if(N == 0 && C == 0){
    return 0;
  }
  A.assign(N,0);
  B.assign(C,0);
  rep(i,0,N - 1){
    rep(j,0,15){
      int a;
      cin >> a;
      A[i] += a * (1LL << j);
    }
  }
  rep(i,0,C - 1){
    rep(j,0,15){
      int a;
      cin >> a;
      B[i] += a * (1LL << j);
    }
  }
 
  rep(i,0,N - 1){
    rep(s,0,(1 << 16) - 1){
      rep(j,0,C - 1){
        auto & to = dp[i + 1][(s | A[i]) & ~(B[j])];
        to = max(to , dp[i][s] + __builtin_popcount((s | A[i]) & B[j]));
      }
    }
  }
 
  int ans = 0;
  rep(s,0,(1 << 16) - 1){
    ans = max(ans,dp[N][s]);
  }
 
  cout << ans << endl;
  return 1;
}
 
int main(){
  while(solve());
}

まだ議論の余地がアリそうですね...(気分っていうのもあるかもしれない)