dp[s][a]已询问{s}有{a}特征,还需要查询几次才能明确是哪一样物品。

答案为dp[0][0].

#include
      
       using namespace std;#define ll long longll n,m;short dp[2050][2050];ll a[200],s0;int main(){    freopen("p.in","r",stdin);    ios::sync_with_stdio(false);    cin>>m>>n;    while(n+m!=0){        memset(dp,0,sizeof(dp));    for(int i=1;i<=n;i++){    ll sum=0,x;    char c;    for(int j=1;j<=m;j++){    cin>>c;    if(c=='0')x=0;else x=1;    sum=sum*2+x;    }    a[i]=sum;    }    for(int s=(1<
       
        =0;s--){     s0=s;     while(1){     bool az=1;     ll cnt=0;     for(int j=1;j<=n;j++){         ll tmp=a[j]&s;         if(tmp==s0)cnt++;         if(cnt>1){az=0;break;}         }    if(az)dp[s][s0]=0;else{    ll miner=1000;    for(int i=1;i<=m;i++){        ll u=1<<(i-1);        if((u&s)==0){        ll q;        q=max(dp[s|u][s0|u],dp[s|u][s0]);        miner=min(q,miner);        }        }        dp[s][s0]=miner+1;}        if(!s0)break;        s0=(s0-1)&s;    }}    cout<
        
         <
         
          >m>>n;    }    return 0;}