【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 <bits/stdc++.h>

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<int,int> pii;

typedef pair<LL,LL> 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;

}