UVa 1252 Twenty Questions (状压DP+记忆化搜索)

时间：2023-03-08 18:05:47
UVa 1252 Twenty Questions (状压DP+记忆化搜索)

题意：有n件物品，每件物品有m个特征，可以对特征进行询问，询问的结果是得知某个物体是否含有该特征，要把所有的物品区分出来（n个物品的特征都互不相同），

最小需要多少次询问？

析：我们假设心中想的那个物体为W，首先知道的是，同一个特征不用问多次，所以首先用一个集合s表示已经问的特征，在这里面有的是W具备的，有的不是，

所以再加一个集合a表示W所以具备的特征，并且a是s的子集。d(s, a) 表示问了特征集s，其中已经确认W所具备的特征集为a时，还要询问的最少次数。

再加一个状态，继续询问呗，所以次数就是max{d(s+{k}, a+{k}), d(s+{k}, a)}+1，其中k是下一个特征。

边界就是：如果一个物体满足 具备a中的所有特征，但是不具备s-a中的所有特征。这就是边界。返回0.

代码如下：

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

#include <vector>

#include <map>

#include <cctype>

#include <stack>

#include <sstream>

using namespace std ;

typedef long long LL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const double inf = 0x3f3f3f3f3f3f;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int maxn = 130 + 5;

const int mod = 1e9 + 7;

const char *mark = "+-*";

const int dr[] = {-1, 0, 1, 0};

const int dc[] = {0, 1, 0, -1};

int n, m;

inline bool is_in(int r, int c){

    return r >= 0 && r < n && c >= 0 && c < m;

}

inline int Min(int a, int b){ return a < b ? a : b; }

inline int Max(int a, int b){ return a > b ? a : b; }

int d[1<<11][1<<11];

int st[maxn];

char ss[15];

void init(int i){

    for(int j = 0; j < m; ++j)

        if(ss[j] == '1')  st[i] |= (1<<j);

}

int dp(int s, int a){

    int &ans = d[s][a];

    if(ans >= 0)  return ans;

    int cnt = 0;

    for(int i = 0; i < n; ++i)

        if((st[i] & s) == a) ++cnt;

    if(cnt <= 1)  return ans = 0;//如果这样的物体只有1个，或者没有就可以区别了

    ans = INF;

    for(int i = 0; i < m; ++i){

        if(s & (1<<i))  continue;

        ans = Min(ans, Max(dp(s|(1<<i), a|(1<<i)), dp(s|(1<<i), a))+1);//加一个特征

    }

    return ans;

}

int main(){

    while(scanf("%d %d", &m, &n) == 2){

        if(!m && !n)   break;

        memset(st, 0, sizeof(st));

        for(int i = 0; i < n; ++i){

            scanf("%s", ss);

            init(i);

        }

        memset(d, -1, sizeof(d));

        int ans = dp(0, 0);

        printf("%d\n", ans);

    }

    return 0;

}

　　

相关文章