Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2011-01-19

PKU 3809 -- Twenty Questions

| 19:25 | PKU 3809 -- Twenty Questions - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3809 -- Twenty Questions - Wrong Answer -- japlj PKU 3809 -- Twenty Questions - Wrong Answer -- japlj のブックマークコメント

311 でメモ化再帰した。TLE厳しい感じ。


#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int pow3[11], obj[128], memo[200000];
int b, n;

int rec(int st, int cand, int mask, int bits)
{
  if(memo[st]>=0) return memo[st];
  if(cand <= 1) return memo[st] = 0;
  int& ret = memo[st];
  ret = n;
  for(int i=0; i<b; ++i) {
    if(st/pow3[i]%3==0) {
      int cnt = 0;
      for(int k=0; k<n; ++k) {
	bool ok = (obj[k] & (mask | (1<<i))) == bits;
	if(ok) cnt++;
      }
      if(cnt == 0 || cnt == cand) continue;
      ret = min(ret, 1 +
		max(rec(st+pow3[i], cnt, mask|(1<<i), bits),
		    rec(st+pow3[i]*2, cand-cnt, mask|(1<<i), bits|(1<<i))));
    }
  }
  return ret;
}

int main()
{
  pow3[0] = 1;
  for(int i=1; i<=10; ++i) pow3[i]=pow3[i-1]*3;
  while(scanf("%d%d", &b, &n), b||n) {
    for(int i=0; i<n; ++i) {
      char s[12];
      scanf("%s", s);
      obj[i] = 0;
      for(int j=0; j<b; ++j) obj[i]=obj[i]*2+s[j]-'0';
    }
    memset(memo, -1, sizeof(memo));
    printf("%d\n", rec(0, n, 0, 0));
  }
  return 0;
}
 |