0263:Beat Panel
ビットDPで解いた。
dp[ビート音の数][ボタンの押し方]:=得点の最大値
立っているビットの数を数える関数countは
http://tak5219.seesaa.net/article/7042181.html
を参考にした。
#include<iostream> #include<algorithm> #include<cstring> using namespace std; int a[30],b[30],dp[31][1<<16]; int count(int bits){ bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333); bits =(((bits >> 4) + bits) & 0x0f0f0f0f); bits += bits >> 8; return (bits + (bits >> 16)) & 0xff; } int main(void){ int n,c,in; while(cin >> n >> c,n|c){ fill(a,a+n,0); fill(b,b+c,0); for(int i=0;i<n;i++){ for(int j=0;j<16;j++){ cin >> in; a[i] |= in<<(15-j); } } for(int i=0;i<c;i++){ for(int j=0;j<16;j++){ cin >> in; b[i] |= in<<(15-j); } } 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]<0)continue; int now=a[i]|j; for(int k=0;k<c;k++){ int next=now & ~b[k]; dp[i+1][next]=max(dp[i+1][next],dp[i][j]+count(now & b[k])); } } } int ans=0; for(int i=0;i<(1<<16);i++){ ans=max(ans,dp[n][i]); } cout << ans << endl; } return 0; }