uva 1252 - Twenty Questions(记忆化搜索）

题目链接：uva 1252 - Twenty Questions

题目大意：给出m和n，表示有n个长度为m且由01组成的字符串，要求询问k个位置，以区分这n个字符串，每次询问一个位置，将会得到该位置的字符，注意询问k次的位置并非固定：

例：5 4

10100

11000

00001

00010

ans = 2；询问了第1个位置后，区分开了（1）（2）和（3）（4），然而区分（1）（2）只要询问2或者3即可，区分（3）（4）只要询问4或者5即可。

解题思路：记忆化搜索，dp[x][y]表示区分 询问了x（二进制）这几个位置后状态为y的最优次数，每次需要遍历一遍字符串，计算当前有多少个字符串满足询问x状态为y，如果小于等于1即不用再询问就可以区分了；否则要枚举还没询问的位置，然后取max（solve(x|(1<<i), y), solve(x|1<<i), y|(1<<i)) +1;一种是询问返回值为0的情况，一种是返回值为1的情况，考虑最坏情况。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
const int N = 150;
const int M = 12;
const int INF = 0x3f3f3f3f;

int n, m, dp[1<<M][1<<M], s[N];

void init () {
	memset(dp, -1, sizeof(dp));

	char str[M];
	for (int i = 0; i < n; i++) {
		scanf("%s", str);
		int state = 0;
		for (int j = 0; j < m; j++) if (str[j] == '1')
			state = state | (1<<j);
		s[i] = state;
	}
}

int solve (int x, int y) {
	if (dp[x][y] != -1) return dp[x][y];
	dp[x][y] = INF;

	int c = 0;
	for (int i = 0; i < n; i++) {
		if ( (x&s[i]) == y) c++;
	}
	
	if (c <= 1) return dp[x][y] = 0;

	for (int i = 0; i < m; i++) {
		if (x&(1<<i)) continue;
		dp[x][y] = min(dp[x][y], max(solve(x|(1<<i), y), solve(x|(1<<i), y|(1<<i))) + 1);
	}
	return dp[x][y];
}

int main () {
	while (scanf("%d%d", &m, &n) == 2 && n + m) {
		init();
		printf("%d\n", solve(0, 0));
	}
	return 0;
}