UVa1252 Twenty Questions

전설의 상태 압축 DP.어떤 종류의 상태를 2진법으로 압축하다.dp(s,a)는 질문 집합이 s인 것을 대표하고 상태 집합이 a인 것을 확인하는 경우 최소한의 질문 횟수가 필요하다.이 해법은 두 가지 측면에서 묘하다. 첫 번째는 int를 사용하여 하나의 집합을 나타내고 한 이진법은 하나의 원소를 나타낸다. 이것은 모두가 알고 있다.둘째, 경계 조건을 잘 요약하고 어떤 상황에서 더 이상 질문할 필요가 없는지 분석하여 가상의 물체를 설치했는데 사실 이 물체는 모든 존재하는 물체를 가리킬 수 있다.상태가 이동하는 과정에서min함수는 질문을 최적화하기 위해 불필요한 질문을 묻지 않고max함수는 모든 물체 중 가능한 최악의 상황을 고려하기 위한 것이다.구해 과정에서 존재하지 않는 상태를 계산하지만 다행히 존재하지 않는 상태는 결과에 영향을 주지 않는다.
하지만 이 문제는 내가 이해할 수 없는 부분이 있다. 질문할 때 순서는 중요하지 않을 것이다. 그러나 내가 인위적으로 질문 순서를 정하면 WA가 된다.(코드 주석 섹션 참조)

#include <iostream>    
#include <stdio.h>    
#include <cmath>    
#include <algorithm>    
#include <iomanip>    
#include <cstdlib>    
#include <string>    
#include <memory.h>    
#include <vector>    
#include <queue>    
#include <stack>    
#include <map>  
#include <set>  
#include <ctype.h>    
#define INF 10000000
#define ll long long
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define MAXN 100010

using namespace std;  

int obj[130];
int m,n;

int strtobit(char* str){
	int num=0;
	for(int i=0;i<m;i++){
		if(str[i]=='1')num+=(1<<(m-i-1));
	}
	return num;
}

int dp[3000][3000];

int fun(int s,int a){
	if(dp[s][a]!=-1)return dp[s][a];
	int cnt=0;
	for(int i=1;i<=n;i++){
		if( (obj[i]&s)==a)cnt++;
	}
	if(cnt<=1){
		dp[s][a]=0;
		return 0;
	}
	int re=INF;
	
	int k=m;
	/*for(k=0;k<m;k++){
		if( s&(1<<k) ){
			break;
		}
	}*/
	
	while(k--){
		if( s&(1<<k) ) continue;
		int t=1<<k;
		re=min( re , max(fun(s^t,a^t),fun(s^t,a))+1 );
	}

	dp[s][a]=re;
	return re;
}

int main(){
	while(cin>>m>>n){
		if(m==0&&n==0)break;
		memset(dp,-1,sizeof(dp));
		
		char str[15];
		for(int i=1;i<=n;i++){
			cin>>str;
			obj[i]=strtobit(str);
		}
		
		cout<<fun(0,0)<<endl;
	}
	return 0;
}