uva 1252(狀態壓縮dp)

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 
#include 
#include 
#include 
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
, dp(0, 0));
    }
    return 0;
}