首页 > 代码库 > (状压dp)UVA - 1252 Twenty Questions
(状压dp)UVA - 1252 Twenty Questions
题目地址
读入二进制数及转换的方法。
e.g. bitset<16> x;
cin>>x;
cout<<x.to_ulong()<<endl;
1 #include <bits/stdc++.h> 2 typedef long long ll; 3 using namespace std; 4 const int MAX=2e2; 5 const int INF=1e9; 6 int m,n; 7 int a[MAX]; 8 int total; 9 int cnt[1<<11][1<<11];//cnt[x][y]问过x状态,得到y状态的确定答复的可能情况数 10 int dp[1<<11][1<<11];//dp[x][y]问过x状态,得到y状态的答复至少还需问多少次能保证确定 11 bitset<16> x; 12 int d_p(int st_ask,int st_re) 13 { 14 if(dp[st_ask][st_re]>=0&&dp[st_ask][st_re]!=INF) 15 return dp[st_ask][st_re]; 16 if(cnt[st_ask][st_re]<=1) 17 return dp[st_ask][st_re]=0; 18 for(int i=0;i<m;i++) 19 { 20 if(!(st_ask&(1<<i))) //没有问过 21 { 22 int now_max=max(d_p((st_ask|(1<<i)),(st_re|(1<<i))),d_p((st_ask|(1<<i)),(st_re)))+1; 23 dp[st_ask][st_re]=min(dp[st_ask][st_re],now_max); 24 } 25 } 26 return dp[st_ask][st_re]; 27 } 28 int main() 29 { 30 while(scanf("%d%d",&m,&n)&&m) 31 { 32 memset(cnt,0,sizeof(cnt)); 33 for(int i=0;i<n;i++) 34 { 35 cin>>x; 36 a[i]=x.to_ulong(); 37 } 38 total=1<<m; 39 for(int i=0;i<total;i++) 40 for(int j=0;j<total;j++) 41 dp[i][j]=INF; 42 for(int i=0;i<total;i++) 43 for(int j=0;j<n;j++) 44 ++cnt[i][i&a[j]]; 45 printf("%d\n",d_p(0,0)); 46 } 47 return 0; 48 }
(状压dp)UVA - 1252 Twenty Questions
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。