UVA-1252 Twenty Questions （状压ＤＰ）

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

题目分析：定义dp(s,a)表示询问了的特征集合为s，物体含有特征集合a中的所有特征，但不含特征集合 s^a 中的所有特征时还需的最少询问次数。状态转移方程为dp(s,a)=min(max(dp(s|(1<<k),a|(1<<k)),dp(s|(1<<k),a))+1)。用记忆化搜索的形式实现即可。

当这样的物体只有一个或一个没有时，便可区分出所有的物品，此时dp(s,a)=0。

代码如下：

# include<iostream>

# include<cstdio>

# include<string>

# include<cstring>

# include<algorithm>

using namespace std;

const int INF=0x3f3f3f3f;

char p[13];

int dp[1<<11][1<<11],sta[130],m,n;

int getVal()

{

    int res=0;

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

        if(p[i]=='1')

            res|=(1<<i);

    return res;

}

int DP(int s,int a)

{

    if(dp[s][a]!=INF)

        return dp[s][a];

    int num=0;

    for(int i=0;i<n;++i)///在这里，也可以预处理出来以提高效率；

        if((sta[i]&s)==a)///"=="的优先级比"&"的高!!!

            ++num;

    if(num<=1)

        return dp[s][a]=0;

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

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

        if(s&(1<<i))

            continue;

        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)&&n+m)

    {

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

            scanf("%s",p);

            sta[i]=getVal();

        }

        memset(dp,INF,sizeof(dp));

        printf("%d\n",DP(0,0));

    }

    return 0;

}

巴特西

UVA-1252 Twenty Questions （状压ＤＰ）

最新文章

热门文章