はやし屋

競技プログラミングのメモ きたない

AOJ 0263: Beat Panel

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

消える処理考えるのに時間がかかったbitdp

メモ化

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

int n ,c ;
int dp[1<<16][33];
vector < int > pat , can;

int in(){
  int ret = 0;
  for(int i = 15; i >= 0 ; --i){
    int k;scanf("%d",&k);
    ret += k << i;
  }
  return ret;
}

int solve(int npat,int idx){
  if(idx == n)return 0;
  if(~dp[npat][idx])return dp[npat][idx];
  int ret = 0 ;
  for(int i = 0 ; i < c ; ++i){
    int getpoint = __builtin_popcount(npat&can[i]);
    ret = max(ret,solve(((npat^can[i])&npat)|pat[idx+1],idx+1)+getpoint);
  }
  return dp[npat][idx] = ret;
}
 
int main(){
  while(scanf("%d%d",&n,&c)&&(n|c)){
    pat.clear();can.clear();
    for(int i = 0 ; i < n ; ++i)
      pat.push_back(in());
    for(int i = 0 ; i < c ; ++i)
      can.push_back(in());
    pat.push_back(0);
    can.push_back(0);
    memset(dp,-1,sizeof(dp));
    printf("%d\n",solve(pat[0],0));
  }
}

for

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

int n ,c;
vector < int > pat , can;
int dp[33][1<<16];

int in(){
  int ret = 0;
  for(int i = 15; i >= 0 ; --i){
    int k;scanf("%d",&k);
    ret += k << i;
  }
  return ret;
}
 
int main(){
  while(scanf("%d%d",&n,&c)&&(n|c)){
    pat.clear();can.clear();
   
    for(int i = 0 ; i < n ; ++i)
      pat.push_back(in());
    for(int i = 0 ; i < c ; ++i)
      can.push_back(in());
    pat.push_back(0);
    can.push_back(0);
    memset(dp,-1,sizeof(dp));
    dp[0][pat[0]] = 0;
    for(int i = 0 ; i < n ; ++i){
      for(int j = 0 ; j < (1<<16) ; ++j){
	if(~dp[i][j]){
	  for(int k = 0 ; k < c ; ++k){
	    dp[i+1][((j^can[k])&j)|pat[i+1]] = max(dp[i+1][((j^can[k])&j)|pat[i+1]],__builtin_popcount(j&can[k]) + dp[i][j]);
	  }
	}
      }
    }
    printf("%d\n",max(*max_element(dp[n],dp[n]+(1<<16)),0));
  }
}