UVA1252[Twenty Questions] 状态压缩动态规划模型

题目链接

题目大意：有n个长度为m的二进制串，每个都是不同的。为了把所有字符串区分开，你可以询问，每次可以问某位上是0还是1。问最少提问次数，可以把所有字符串区分开来。

状态压缩动态规划

由于状态太多，转移太复杂，通常要开很多维数组，所以可以用二进制来表示状态，这样转移比较方便。

dp[i][j] 表示 集合i和集合j状态的答案

解题报告：d(s,a) 表示已经询问过s集合中满足特性的集合a时询问最小次数。

dp[s][a]=min( max( dp[s+{k}][a], dp[s+{k}][a+{k}] ) )

取max是考虑最坏情况

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 150;
const int M = 13;int n, m, dp[1<<M][1<<M], cnt[1<<M][1<<M], p[N];void init(){for ( int i=0; i<(1<<m); i++ )for ( int j=0; j<n; j++ ) cnt[i][p[j]&i]++;
}int d(int s, int a){
// printf("%d %d\n", dp[s][a], cnt[s][a]);if( dp[s][a]!=2139062143 ) return dp[s][a];if( cnt[s][a]<=1 ) return 0;for ( int i=0; i<m; i++ ){if( s&(1<<i) ) continue;dp[s][a]=min(dp[s][a], max(d(s|(1<<i),a),d(s|(1<<i),a|(1<<i)) ) );}dp[s][a]++;return dp[s][a];
}int main(){while( scanf("%d%d", &m, &n)==2 && n && m ){for ( int i=0; i<n; i++ ){p[i]=0;char ss[13];scanf("%s", ss);for ( int j=0; j<m; j++ ) if( ss[j]=='1' ) p[i]|=(1<<j);}// for ( int i=0; i<n; i++ ) printf("%d\n", p[i]);memset(cnt,0,sizeof(cnt));memset(dp,0x7f,sizeof(dp));init();printf("%d\n", d(0,0) );}
}