首页 > 代码库 > UVa 1252 (状压DP + 记忆化搜索) Twenty Questions
UVa 1252 (状压DP + 记忆化搜索) Twenty Questions
题意：
有n个长为m的各不相同的二进制数(允许存在前导0)，别人已经事先想好n个数中的一个数W，你要猜出这个数。
每次只可以询问该数的第K为是否为1.
问采用最优询问策略，则最少需要询问多少次能保证猜到。
比如有1100 和 0110两个数，只需要询问第一或第三位数是否为1，即可猜中，因此答案为1.
分析：
d(s, a)表示已经询问了的集合s，在已经询问了的集合中W中为1的集合为a，还需要询问多少次。
如果下一次询问第k位，则询问次数为：
然后取所有k里的最小值即可。
预处理：
对于每个s和a，可以先把满足条件的数的个数记录下来，保存在cnt[s][a]里。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 6 const int maxm = 12, maxn = 130; 7 char object[maxn][maxm + 10]; 8 int d[1<<maxm][1<<maxm], cnt[1<<maxm][1<<maxm], vis[1<<maxm][1<<maxm]; 9 int m, n, kase = 0;10 11 int dp(int s, int a)12 {13 if(cnt[s][a] <= 1) return 0;14 if(cnt[s][a] == 2) return 1;15 16 int& ans = d[s][a];17 if(vis[s][a] == kase) return ans;18 vis[s][a] = kase;19 20 ans = m;21 for(int k = 0; k < m; ++k)22 {23 if(!(s&(1<<k)))24 {25 int s2 = s | (1<<k), a2 = a | (1<<k);26 if(cnt[s2][a] >= 1 && cnt[s2][a2] >= 1)27 {28 int need = max(dp(s2, a2), dp(s2, a)) + 1;29 ans = min(ans, need);30 }31 }32 }33 return ans;34 }35 36 int main()37 {38 //freopen("in.txt", "r", stdin);39 while(scanf("%d%d", &m, &n) && n)40 {41 ++kase;42 for(int i = 0; i < n; ++i)43 scanf("%s", object[i]);44 memset(vis, 0, sizeof(vis));45 memset(cnt, 0, sizeof(cnt));46 for(int i = 0; i < n; ++i)47 {48 int feature = 0;49 for(int f = 0; f < m; ++f)50 if(object[i][f] == ‘1‘) feature |= (1 << f);51 for(int s = 0; s < (1<<m); ++s)52 cnt[s][s&feature]++;53 }54 printf("%d\n", dp(0, 0));55 }56 57 return 0;58 }
UVa 1252 (状压DP + 记忆化搜索) Twenty Questions
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。