今天给大家说一道UVa1252这道题，这是考我们处理复杂状态的动态规划的题，读题时就十分蒙，不知道我们要怎么猜，

看完题解以及代码后想了想，明白了，下面就说一说这道题吧！

题意：有n（n≤128）个物体，m（m≤11）个特征。每个物体用一个m位01串表示，表示每个特征是具备还是不具备。我在心里想一个物体（一定是这n个物体之一），由你来猜。你每次可以询问一个特征，然后我会告诉你：我心里的物体是否具备这个特征。当你确定答案之后，就把答案告诉我（告知答案不算“询问”）。如果你采用最优策略，最少需要询问几次能保证猜到？例如，有两个物体：1100和0110，只要询问特征1或者特征3，就能保证猜到。

如何猜呢，题意上没说，但是通过题解以及正确代码我们知道就是需要一个个位的猜(如果不是这样猜那么怎么做呢?)，所以我们

接下来就需要求出最少多少次能够猜到。

我们不知道那个人心里想的数字是什么，所以那个人想的数字是什么都可以，所以我们设“心里想的物体”为W，对于W，我们可以

猜测s个集合，这是什么意思呢？就是将s的大小进行二进制的展开，如果某i位是1的话说明我们询问过("那个你猜的数第i位是1

(或0)吗？)这样我们知道一定有些询问符合W的特征而剩下的询问不符合,那么我们将符合W特征的询问用a来表示，所以a一定是

s的子集(想一想，为什么)，设d(s,a)表示已经问了特征集s，其中已确认W所具备的特征集为a时，还需要询问的最小次数。如果

下一次提问的对象是特征k，所以询问次数为

max{d(s+k,a+k),d(s+k,a)}+1

这表明了如果k是W的特征集的情况，以及k不是W的特征集的情况下询问的最大次数，这样我们考虑了W的可能情况，

为了求最小值，我们需要枚举不同的k，然后再上面的最大值中取最小值，得到的最小值说明我们选择这个k能够很快的得到答案

(能够以最少次数猜到那个人心中的数W)。接下来我们说一说动态归划里的边界了，不难得知如果只有一个物体满足“具备集合a中的所有特征”则d(s,a)=0,这样不需要再进行询问了，我们得到了这种情况的答案。

下面说一下时间复杂度以及实现处理，分析一下时间复杂度，由于a是s的子集，s是1-n的子集，所以状态总数为3^m(根据二项式定理得到），

算上决策数为m，所以总的时间复杂度为O(m*3^m)，对于s与a，我们可以事先将满足条件的物体个数求出，存入cnt[s][a]，避免重复计算，

统计cnt[s][a]的方法就是枚举s和物体，时间复杂度为O(n*2^m)，这样总的时间复杂度为O(m*3^m+n*2^m)。

下面是实现：

// UVa 1252#include 
     
       #include 
      
        using namespace std; const int maxn = 128 + 5; const int maxm = 11; int m, n, kase;char objects[maxn][maxm]; int vis[1<
       
        <
        
         = 1 && cnt[s2][a] >= 1) {        int need = max(dp(s2, a2), dp(s2, a)) + 1;          ans = min(ans, need);       }     }  return ans; }void init() {  for (int s = 0; s < (1<
        
       
      
     

from 紫书