Twenty Questions UVA

代码参考刘汝佳

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<assert.h>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<sstream>
#include<stack>
#include<queue>
#include<string>
#include<bitset>
#include<algorithm>
#pragma warning(disable:4996)
#define me(s)  memset(s,0,sizeof(s))
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;const int maxn = 128;
const int maxm = 11;int kase, n, m;
char objects[maxn][maxm + 100];int vis[1 << maxm][1 << maxm], d[1 << maxm][1 << maxm];
int t[1 << maxm][1 << maxm]; //联系实际想一下这个题，其实很容易可以想出一种很暴力的解法，特征最多为n,我最多问n次，怎么问，最多有n的阶乘种方案，
//那我直接遍历这n种方案就行了，每种方案什么时候能问出来就停，然后取最少的就行了
//但时间效率实在难以承受，考虑优化，很明显存在重复计算，比如12345，12354，问了12345后，再去问12354，很明显当我们直接用123的结果就行了
//这也是选择动态规划的原因
//具体写法看下面
int dp(int s, int a) {if (t[s][a] <= 1) return 0;  //完全确定了if (t[s][a] == 2) return 1;  //还有有两个物品满足集合a中的特征，那么再问一个就可以确定了int& ans = d[s][a];if (vis[s][a] == kase) return ans;vis[s][a] = kase; ans = m;for (int k = 0; k < m; k++)if (!(s & (1 << k))) { int s2 = s | (1 << k), a2 = a | (1 << k);if (t[s2][a2] >= 1 && t[s2][a] >= 1) {//算一个剪枝吧，如果啥都问不出来，也就不问了，这就相当于基本所有物品都没这个特征int need = max(dp(s2, a2),dp(s2, a)) + 1; //有这个特征没这个特征都用式，并且要取最大的因为要找出所有的ans = min(ans, need);}}return ans;
}void init() {for (int s = 0; s < (1 << m); s++) {for (int a = s; a; a = (a - 1)&s)t[s][a] = 0;t[s][0] = 0;}for (int i = 0; i < n; i++) {int features = 0;for (int f = 0; f < m; f++)if (objects[i][f] == '1') features |= (1 << f);for (int s = 0; s < (1 << m); s++)t[s][s & features]++;                         //预处理出所有结果}
}int main() {memset(vis, 0, sizeof(vis));while (scanf("%d%d", &m, &n) == 2 && n) {++kase;for (int i = 0; i < n; i++) scanf("%s", objects[i]);init();printf("%d\n", dp(0, 0));}return 0;
}