1 /*
2 题意：给出一系列的01字符串，问最少要问几个问题(列)能把它们区分出来
3 状态DP+记忆化搜索：dp[s1][s2]表示问题集合为s1。答案对错集合为s2时，还要问几次才能区分出来
4 若和答案(自己拟定)相差小于等于1时，证说明已经能区分了，回溯。否则还要加问题再询问
5 */
6 /************************************************
7 * Author :Running_Time
8 * Created Time :2015-8-13 10:54:26
9 * File Name :UVA_1252.cpp
10 ************************************************/
11
12 #include <cstdio>
13 #include <algorithm>
14 #include <iostream>
15 #include <sstream>
16 #include <cstring>
17 #include <cmath>
18 #include <string>
19 #include <vector>
20 #include <queue>
21 #include <deque>
22 #include <stack>
23 #include <list>
24 #include <map>
25 #include <set>
26 #include <bitset>
27 #include <cstdlib>
28 #include <ctime>
29 using namespace std;
30
31 #define lson l, mid, rt << 1
32 #define rson mid + 1, r, rt << 1 | 1
33 typedef long long ll;
34 const int MAXN = 128 + 10;
35 const int INF = 0x3f3f3f3f;
36 const int MOD = 1e9 + 7;
37 int dp[(1<<11)+10][(1<<11)+10];
38 int p[MAXN];
39 char str[13];
40 int m, n;
41
42 int DFS(int s1, int s2) {
43 if (dp[s1][s2] != INF) return dp[s1][s2];
44 int cnt = 0;
45 for (int i=1; i<=n; ++i) {
46 if ((p[i] & s1) == s2) cnt++;
47 }
48 if (cnt <= 1) {
49 return dp[s1][s2] = 0;
50 }
51 for (int i=0; i<m; ++i) {
52 if (s1 & (1 << i)) continue;
53 int nex = s1 | (1 << i);
54 dp[s1][s2] = min (dp[s1][s2], max (DFS (nex, s2), DFS (nex, s2 ^ (1 << i))) + 1);
55 }
56
57 return dp[s1][s2];
58 }
59
60 int main(void) { //UVA 1252 Twenty Questions
61 while (scanf ("%d%d", &m, &n) == 2) {
62 if (!m && !n) break;
63 for (int i=1; i<=n; ++i) {
64 scanf ("%s", str); p[i] = 0;
65 for (int j=0; j<m; ++j) {
66 if (str[j] == '1') {
67 p[i] |= (1 << j);
68 }
69 }
70 }
71 memset (dp, INF, sizeof (dp));
72 printf ("%d
", DFS (0, 0));
73 }
74
75 return 0;
76 }
状压DP+记忆化搜索 UVA 1252 Twenty Questions
编译人生，运行世界！