题目链接:http://fastvj.rainng.com/contest/307763#problem/E
题目大意:
思路:就是要求最坏情况下用最好的策略猜到这个数字,最坏情况:每次的询问,回答结果都是偏向次数多的情况。
最好情况:每次选择询问的位置。
思考:状压dp是一种优雅的暴力。复杂度往往是指数级。考虑了所有的情况。
#include<bits/stdc++.h>
using namespace std;
int st[150];
int dp[(1<<11)+1][(1<<11)+1];
int n, m;
int dfs(int s, int a)
{
if(dp[s][a]!=-1)
{
return dp[s][a];
}
int num=0;
for(int i=1;i<=n;i++)
{
if((s&st[i])==a)
{
num++;
}
}
//这种情况已经能够唯一确定或者没有这个情况时不用再猜了
if(num<=1)
{
return 0;
}
dp[s][a]=(10000000);
for(int i=1;i<=m;i++)
{
if((s&(1<<i-1))==0)
{
//max最坏情况下的min最好策略
dp[s][a]=min(dp[s][a], max(dfs(s|(1<<i-1), a), dfs(s|(1<<i-1), a|(1<<i-1)))+1);
}
}
return dp[s][a];
}
int main()
{
while(scanf("%d%d",&m,&n),n*m)
{
memset(dp, -1,sizeof(dp));
memset(st, 0, sizeof(st));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int x;
scanf("%1d",&x);
st[i]|=(x<<(j-1));
}
}
cout<<dfs(0, 0)<<endl;
}
return 0;
}