uva 1252——Twenty Questions

Bertha 。 2022-08-18 02:41 15阅读 0赞

题意：给定n个物品，每个物品用01串表示，表示具备与否某个特征，然后每次可以询问一个特征，问最少询问几次能够确定一个物品。

思路：状压Dp，将这些数的特征压缩成一个数，把询问过的和没询问的都用一集合表示，然后枚举没有询问的记忆化搜索。

code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <list>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=9999999;
    const int inf=-INF;
    const int N=135;
    const int M=2048+472;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define ft(i,s,n) for (int i=s;i<=n;i++)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    int n,m,d[M][M],cnt[M][M];
    string v[N];
    
    int dp(int s,int a)
    {
        int& ans=d[s][a];
        if (cnt[s][a]<=1) return ans=0;
        if (ans>=0) return ans;
    
        ans=m;
        ft(i,0,m-1)
        if (!(s&(1<<i)))
            ans=min(ans,max(dp(s|(1<<i),a),dp(s|(1<<i),a|(1<<i)))+1);
        return ans;
    }
    int main()
    {
        while (~scanf("%d %d",&m,&n),m+n)
        {
            cls(d,-1);cls(cnt,0);
            ft(i,0,n-1) cin>>v[i];
            ft(i,0,n-1)
            {
                int t=0;
                ft(j,0,m-1) if (v[i][j]!='0') t|=(1<<j);
                ft(j,0,(1<<m)-1) cnt[j][t&j]++;
            }
            printf("%d\n",dp(0,0));
        }
    }