AOJ 0263 - Beat Panel (ビートパネル)
解法
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(); } }