AOJ 0263 - Beat Panel (ビートパネル)

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0263
日本語なので省略。

解法

bitDPで解けました。
具体的には、

dp[何回目のビート音まで鳴ったか][ボタンの光り方] = 最大のスコア
dp[31][1<<16]

で解けました。
計算量としては、上記の見た目上の計算量に加えて、どの押し方を試して遷移するかが掛かります。
なので、

O(n * 2^16 * c)
... 定数省いたら O(nc)

となります。
制約の最大値であれば、6000万程度になりますね。
AOJのスペックなら普通に間に合う感じです。

コード

__builtin_popcount関数は結構便利です。
是非覚えておきたいところ。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int n, c;
int a[31], b[31];
int dp[31][1 << 16];

void solve(){
  memset(dp, -1, sizeof(dp));
  dp[0][0] = 0;

  for(int i = 0; i < n; i++){
    for(int j = 0; j < (1 << 16); j++){
      if(dp[i][j] == -1) continue;

      int nj = (j | a[i]);

      for(int k = 0; k < c; k++){
        int cal = (nj & b[k]);
        int pop = __builtin_popcount(cal);
        dp[i + 1][nj - cal] = max(dp[i + 1][nj - cal], dp[i][j] + pop);
      }
    }
  }

  int ans = 0;
  for(int i = 0; i < (1 << 16); i++){
    ans = max(ans, dp[n][i]);
  }
  cout << ans << endl;
}

int main(){
  while(cin >> n >> c, n){
    for(int i = 0; i < n; i++){
      a[i] = 0;
      for(int j = 0; j < 16; j++){
        int x;
        cin >> x;
        a[i] = (a[i] << 1) + x;
      }
    }

    for(int i = 0; i < c; i++){
      b[i] = 0;
      for(int j = 0; j < 16; j++){
        int x;
        cin >> x;
        b[i] = (b[i] << 1) + x;
      }
    }

    solve();
  }
}