UVA1252 20个问题 Twenty Questions

· · 题解

一、前言

本题是一道状压 DP，由于本人状压 DP学的不好，故写下这篇题解加深理解。本文将介绍位运算，状压 DP，以及做题思路。

二、位运算

操作 集合表示 位运算语句
交集 a \ \cap \ b a & b
并集 a \ \cup \ b a | b
补集 \bar{a} ~ a (全集为二进制都是一)
差集 a \ b a & (-b)
对称差 a \triangle b a ^ b

三、题意

有 n 个长度为 m 的二进制串（物品），每次你都可以询问目标二进制串（心中想的物品）第 k 位的值（心中的物品是否有该特征），问最少询问几次能够确定目标二进制串。

四、思路

（1） 审题

首先看到二进制串就很快能想到状压 DP，再一看 m \leq 11，十分符合状压 DP 的情况。

适合状态压缩的情况：

（2） 状态

由于我们在询问过一个特征值之后就不需要再询问一遍，因此我们可以设一个集合 s 表示已经询问过的特征组成的集合。而我们又要求出一个确定的二进制串，假设这个确定的二进制串为 F，那么我们设 a 表示已经确定的 F 的特征所组成的集合。则可以得到状态 f(s,a) 为已经询问过集合 s，已经确定的 F 的特征集为 a 时还需要询问的最小次数。

（3） 转移

我们假设下一次提问的对象是特征 k，可得转移方程

f(s,a)=\min(f(s,a),\max(f(s+\{k\},a+\{k\}),f(s+\{k\},a))+1)

取 \max 是因为我们只是猜测确定的串是否有特征 k，它可能有可能没有，需要我们取最大值保证确定了 k 到底是不是它的特征。取 \min 得到满足条件的最优解。

（4） 实现

具体实现用记忆化搜索更优，因为这里我们难以确定递推顺序，而记忆化搜索不需要考虑顺序。

五、状压 DP

接下来我会举一些本题的代码为例子来阐述状压 DP 的具体实现。

(s&(1<<k))==0;
s|(1<<k);
for(int i = s; i; i = (i-1)&s)

六、后记