UVa 1252 20个问题

题意：

有n个物体，m个特征。每个物体用一个m位01串表示，表示每个特征是具备还是不具备。我在心里想一个物体，由你来猜。

你每次可以询问一个特征，然后我会告诉你：我心里的物体是否具备这个特征。当你确定答案之后，就把答案告诉我。如果你采用最优策略，最少需要询问几次就能保证猜到。

思路：

很明显的状压DP,和校长的烦恼那道题目差不多，可以用记忆化搜索。

d[s][a]中的s表示询问的总特征集，a表示所想物体所具备的特征集，因此a一定是s的子集。

 1 #include<iostream> 
 2 #include<cstring>
 3 #include<string>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 
 8 const int maxn = 1 << 12;
 9 const int INF = 0x3f3f3f3f;
10 
11 string str;
12 int w[130];
13 int d[maxn][maxn];
14 int m, n;
15 
16 int dp(int s, int a)
17 {
18     int& ans = d[s][a];
19     if (ans != INF)  return ans;
20     int cnt = 0;
21     for (int i = 0; i<n; i++)
22         //边界条件判断，如果cnt<=1，则说明能判断出来了
23     if ((w[i] & s) == a)  cnt++;
24     if (cnt <= 1){ d[s][a] = 0; return 0; }
25 
26     for (int i = 0; i<m; i++)
27     {
28         if (s&(1 << i))continue;
29         ans = min(ans, max(dp(s | 1 << i, a | 1 << i), dp(s | 1 << i, a)) + 1);
30     }
31     return ans;
32 }
33 
34 int main()
35 {
36     //freopen("D:\txt.txt", "r", stdin);
37     while (cin>>m>>n &&n&&m)
38     {
39         memset(w, 0, sizeof(w));
40         memset(d, INF, sizeof(d));
41         for (int i = 0; i<n; i++)
42         {
43             cin >> str;
44             for (int j = 0; str[j]; j++)
45             if (str[j] == '1')  w[i] |= (1 << j);
46         }
47         printf("%d
", dp(0,0));
48     }
49 }