【Link】:

【Description】

给你n个物体,每个物体都有m种属性;

(每个物体的属性都能和别的物体的属性区别)

现在,你已知这n个物体;

然后让一个人心里想一个物体

你可以问这个人,这个物体是否有第i个属性;

显然,这样最后是肯定能问出来你心里所想的那个物体的;

问你,在最坏的情况下,最少要问多少次才够;

【Solution】

首先,需要明确,每个属性最多问一次

问哪些属性是决定最后结果的关键;

所以在写dp的时候;

我们需要确定下一个需要选择问哪个属性,以及这个问题的答案是什么,因为我们不确定最坏的情况是哪一个物体产生的,所以,对于每一种答案,yes或者是no,都应该考虑到;

于是,我们枚举提了哪一些问题,同时,对每个问题是”yes”或者”no”都考虑到;

写成记忆化搜索的形式

int dfs(int s,int a)

这里的s是提的问题的集合,而a是针对每个问题的回答,如果为1,表示那个属性在,否则不在;

进入递归之后;

先算出,有多少个物品,在提问为s的时候,回答就是a,记为tot;

如果tot<=1,则说明,已经可以确定了,那个唯一的物品就是答案了;

则返回0,表示不用再问问题了,如果tot为0,则表示没有物品符合这个情况,则也返回0即可,为什么返回0也可以?因为我们在枚举下面要问哪个问题的时候取了max;

如果tot>1

则说明,现在还不能确定答案;

则再尝试问下一个问题.

问下一个问题的时候,在回答为yes或no中,要取max,因为你要考虑的是最坏的情况;

然后对于每个问题,则是取最小的,因为你可以改变问的问题,规避次数多的,这是你可以控制的;

---

UPD1

我们是以选择了哪个属性作为阶段的,选择了一个属性之后,就相当于问题转化为,第x个属性选择的是第y属性之后,最坏的情况的最小值.

所以第x个属性,我们可以做决策,选最小的那个.

---

UPD2

对于选择了相同的属性,选择的顺序不同,得到的结果也是不同的;

因为可能某一个顺序,在一半就已经能够确定了,而另外一个顺序要多一点才能确定答案。

【NumberOf WA】

0

【Reviw】

枚举所有的可能,覆盖最坏的情况,寻找最优解.

【Code】

#include 
     
      using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define ms(x,y) memset(x,y,sizeof x)#define Open() freopen("D:\\rush.txt","r",stdin)#define Close() ios::sync_with_stdio(0)typedef pair
      
        pii;typedef pair
       
         pll;const int dx[9] = {
    0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {
    0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int N = 128;const int M = 11;const int MM = 2048;const int INF = 10e8;int m,n,sta[N+10],two[M+10],f[MM+10][MM+10];int cnt[MM+10][MM+10];char ss[M+10];int dfs(int s,int a){    if (f[s][a]!=INF) return f[s][a];    int &t = f[s][a],tot = 0;    if (cnt[s][a]!=INF)        tot = cnt[s][a];    else{        rep1(i,1,n)            if ( (sta[i]&s)==a)                tot++;        cnt[s][a] = tot;    }    if (tot <= 1) return t = 0;    rep1(i,0,m-1)        if ((s&two[i]) == 0){            t = min(t,max(dfs(s|two[i],a),dfs(s|two[i],a|two[i]))+1);        }    return t;}int main(){    //Open();    //Close();    two[0] = 1;    rep1(i,1,M) two[i] = two[i-1]*2;    while (~scanf("%d%d",&m,&n) && m &&n){        rep1(i,0,MM)            rep1(j,0,MM)                f[i][j] = cnt[i][j] = INF;        rep1(i,1,n){            sta[i] = 0;            scanf("%s",ss);            rep1(j,0,m-1)                if (ss[j]=='1')                    sta[i] |= two[j];        }        printf("%d\n",dfs(0,0));    }    return 0;}