UVA 1252 Twenty Questions——dp

UVA 1252 Twenty Questions——dp

做这道题深刻意识到自己智商不够。。。。。。

A和B正在玩这个游戏，B拿着一个物品清单（每个物品有S个特征）随机选了一件（设为X）让A猜，然后A就开始问，每问一次就能确定X的一个特征，问A最少问多少次可以猜出X是哪一个物品。

A每次问的时候无非就是选择一个没问过的特征k，然后根据B的答案确定X是否具有特征k，基于这一点我们可以定义状态，用dp【i】【j】表示当前问过的特征集合为i，已确定物品X具有的特征集合为j（j一定是i的子集），这个状态下最少需要多少次询问才能确定X，结果就是dp【0】【0】

将状态转移之前要先说说边界，因为做完以后发现这道题正真卡我的地方就是边界。这题的边界很玄学，因为它不确定，有多选一的意思，导致从边界逆推变得十分困难（至少我想不出来、、、），只能从状态（0,0）正推入手。

当A询问时，影响结果的其实是询问的顺序。现在从dp【0】【0】出发，A可以询问特征1~S的任一个（假设为k），k的不同就决定了结果的不同。当选了一个k后，A要获得B的答案来确定X是否有状态k，但是正推过程中A根本不知道B的答案是什么，也就是说X可能有特征k也可能没特征 k，那么dp【0】【0】和dp【0+{k}】【0+{k}】、dp【0+{k}】【0】之间的关系是怎样的呢？你要明确你选择的最终目的是确定X，因为你不知道当前决策是有k还是没有k，所以要保证两种情况下都能确定X（这是本题的核心，仔细思考），经过以上的讨论，我们确定了状态转移方程

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

if(x&(1<

dp[x][y] = min(dp[x][y], max(dfs(x|(1<

}

最后详细讲一下边界问题，边界就是某个状态下唯一确定一个物品，这个可以遍历状态x和物品y，用cnt【x】【y】记录当前状态下能确定的物品数量，cnt【x】【y】为1的状态就是边界，此时dp【x】【y】=0。注意cnt【x】【y】为0的状态是错误状态，为了不让其影响结果，我们令其对应的dp【x】【y】 = 0(这和上面的max有关，想一下)。其余的dp【x】【y】赋值为INF就可以了

#include #include #include #include using namespace std;const int maxn = 1<<11;const int INF = 0x3f3f3f3f;char str[20];int s, n, cnt[maxn][maxn], dp[maxn][maxn];int dfs(int x, int y) { if (cnt[x][y] <= 1) return dp[x][y] = 0; if (dp[x][y] != INF) return dp[x][y]; for (int i = 0; i < s; i++) { if(x&(1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。