UVA 1252 - Twenty Questions（状态压缩DP+记忆化搜寻）

UVA 1252 - Twenty Questions（状态压缩DP+记忆化搜索）

题意：01特征串组成的物品，现在你可以询问一个位置的特征，对于每个东西如果为1回答YES，如果为0回答NO。那么如果你当前无法区分开每个东西，就可以继续问一个特征，现在要求最坏情况下，你需要询问几次的最少次数。

思路：枚举询问的位置的所有可能，也就是枚举（1<<m）-1的所有子集，每次询问下一个特征就枚举询问的所有可能，所以会产生重复的子集，所以用记忆化，而且状态仅仅是询问过的特征集合还不够，没办法判断当前的询问是否可以区分开某个物体，所以还要枚举当前询问的特征有或者没有，所以就是枚举特征询问子集的子集，所以状态数接近3^n，每个状态决策m次

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int m,n;
int st[130];
int dp[1<<11][1<<11];
const int inf = 0x3f3f3f3f;
int DP(int s1,int s2)
{
    int &ans=dp[s1][s2];
    if(ans>=0) return ans;
    ans=inf;
    int cnt=0;
    for(int i=1;i<=n;i++)
        if((s1&st[i])==s2) cnt++;
    if(cnt<=1)
        return ans=0;
    for(int i=0;i<m;i++)
        if((s1&(1<<i))==0)
            ans=min(ans,max(DP(s1|(1<<i),s2),DP(s1|(1<<i),s2^(1<<i)))+1);
    return ans;
}
int main()
{
    while(~scanf("%d%d",&m,&n)&&(n||m))
    {
        for(int i=1;i<=n;i++)
        {
            char str[15];
            int t=0;
            scanf("%s",str);
            for(int j=0;str[j];j++)
                if(str[j]=='1')
                    t|=(1<<j);

            st[i]=t;
        }
        memset(dp,-1,sizeof(dp));
        printf("%d\n",DP(0,0));
    }
}