aoj1302:Twenty Questions
解法
各桁について、「未質問」「質問したら1だった」「質問したら0だった」の3通りの状態がありうる。
M<=11なので、O(3^M)は十分に現実的。
よって、いい感じにメモ化再帰を行うことで幸せになる。
コード
#include<bits/stdc++.h> using namespace std; #define int long long typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define all(v) (v).begin(),(v).end() #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define pb push_back #define fi first #define se second template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} int en(vint &v){ int ret=0; rep(i,v.size()){ ret=ret*3+v[i]; } return ret; } int M,N; int memo[81*81*27]; int dfs(vint lis,vint v){ int c=en(v); if(memo[c]!=-1)return memo[c]; if(lis.size()==1)return 0; int &ret=memo[c]; ret=1001001001; rep(i,M){ bool ok=false; rep(j,lis.size())if((lis[j]>>i&1)!=(lis[0]>>i&1))ok=true; if(!ok)continue; vint x,y; rep(j,lis.size()){ if((lis[j]>>i&1))x.pb(lis[j]); else y.pb(lis[j]); } vint a,b; a=v;b=v; a[i]=1;b[i]=2; chmin(ret,max(dfs(x,a),dfs(y,b))+1); } return ret; } signed main(){ while(cin>>M>>N,M||N){ vector<int>lis; rep(i,N){ string s; int b; cin>>s; rep(j,s.size()){ b=b*2+s[j]-'0'; } lis.pb(b); } vector<int>v(M); memset(memo,-1,sizeof(memo)); cout<<dfs(lis,v)<<endl; } return 0; }