uva 1252(状态压缩dp)

题意：有n个二进制串，长度都是m且都不相同，问最少询问多少个问题可以把这n个串完全区分开。
题解：1<=m<=11，从这个范围就可以推测是状态压缩，那么dp肯定要有一维表示提问的问题，然后另一位就是根据提出的问题把串分类，一种是符合提出的问题的状态，另一种不符合。这样f[i][j]表示在问了问题i的状态下答案是状态j时还要提出多少个问题才能把所有串区分开。
如果找到在问题i下和答案j相同的串只有1串或没有，说明f[i][j]=0不需要再提问就已经区分开了，否则就要再提问问题，把之前问题i的位上是0的变为1，答案在该位变1的和保持不变的dp返回值中选出较大值(因为两边最后都要区分开，选问题数多的才可以)。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 135;
const int M = (1 << 11) + 5;
int n, m, a[N], f[M][M];
char str[15];

int dp(int s1, int s2) {
    if (f[s1][s2] != INF)   
        return f[s1][s2];
    int cnt = 0;
    for (int i = 0; i < n; i++)
        if ((s1 & a[i]) == s2)
            cnt++;
    if (cnt <= 1)
        return f[s1][s2] = 0;
    for (int i = 0; i < m; i++) {
        if (s1 & (1 << i))
            continue;
        int temp = s1 | (1 << i);
        f[s1][s2] = min(f[s1][s2], max(dp(temp, s2), dp(temp, s2 ^ (1 << i))) + 1);
    }
    return f[s1][s2];
}

int main() {
    while (scanf("%d%d", &m, &n) == 2 && n + m) {
        memset(f, INF, sizeof(f));
        for (int i = 0; i < n; i++) {
            scanf("%s", str);
            a[i] = 0;
            for (int j = 0; j < m; j++)
                if (str[j] == ‘1‘)
                    a[i] |= (1 << j);
        }
        printf("%d\n", dp(0, 0));
    }
    return 0;
}