首页 > 代码库 > uva 1252 Twenty Questions 状压dp
uva 1252 Twenty Questions 状压dp
集合上的dp,看小紫书想了好久~
有n个物体,m个特征,最少询问多少次能保证猜到是哪个问题。
首先在读入的时候将每个物体转化为一个二进制整数,用一个集合s来表示已经询问了哪些特征。
用d(s,a)来表示询问了集合s的特征,有集合a个特征已经具备,还需要问多少个特征的最小值。a一定为s的子集。
则状态方程为 d(s,a) = min{ max(d(s+{k},a+{k}),(s+{k},a) )+1 ,| {k}?s}。边界条件为,若只有一个物体具有a的特征,且不具有s-a的特征,则d(s,a)=0;
#include<cstdio> #include<cstring> #include<algorithm> #define mem(name,value) memset(name,value,sizeof(name)) using namespace std; const int maxn=130; const int maxm=11; const int inf=0x3f3f3f3f; int d[1<<maxm][1<<maxm]; int cnt[1<<maxm][1<<maxm]; int p[maxn],n,m; char t[maxm+3]; void init(){ mem(cnt,0); mem(d,-1); for(int i=0;i<n;i++){ scanf("%s",t); int la= strlen(t); for(int j=0;j<la;j++) p[i] = (p[i]<<1)+t[j]-48; //物体转换为二进制整数 } for(int i=0;i<(1<<m);i++) //预处理每个状态有多少个物体满足 for(int j=0;j<n;j++) cnt[i][i & p[j]]++; //每个物体在状态i下满足的状态(就是询问了集合i中有哪些特征满足) } int dp(int s0,int s1){ if(d[s0][s1]!=-1) return d[s0][s1]; if(cnt[s0][s1]<=1) return d[s0][s1]=0; //满足这个状态的只有一个物体,则返回值为0 d[s0][s1]=inf; for(int i=0;i<m;i++){ if(s0 & (1<<i)) continue; //只能询问还没有询问过的 int& ans = d[s0][s1]; int t0 = s0^(1<<i); ans = min(ans,max(dp(t0,s1),dp(t0,s1^(1<<i)))+1); //因为询问了第i个特征,对不同物体有可能具有或者不具有,而又要保证能够得到是哪个物体,则应取max; //而通过不同的状态来达到当前状态时,则应该取能达到当前状态的min } return d[s0][s1]; } int main(){ // freopen("in.txt","r",stdin); while(~scanf("%d%d",&m,&n) && m && n){ init(); int ans = dp(0,0); //还没有询问任何特征。 printf("%d\n",ans); } return 0; }
uva 1252 Twenty Questions 状压dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。