2.5s低空飘过
集合上的动态规划,中间状态一般就是全集的子集合。为了精确的描述状态,一般增加一个或多个维度。
这道题全集就是所有的特征,中间状态就是询问了某一些特征。询问的结果则要用另一个维度来储存。
动态规划的过程就是把所有可能的询问遍历一遍,在每次遍历的同时,遍历所有的询问结果的可能性。边界值及时返回、重叠子问题及时返回,避免重复运算。
Run Time: 2.542s
#define UVa "LT9-16.1252.cpp" //Twenty Questions char fileIn[30] = UVa, fileOut[30] = UVa; #include<cstring> #include<cstdio> #include<algorithm> #include<ctype.h> using namespace std; //Global Variables. Reset upon Each Case! const int maxm = 11 + 1, maxn = 128 + 5; const int INF = maxm + 5; int m, n; int ft[maxn]; int cnt[1<<maxm][1<<maxm]; int d[1<<maxm][1<<maxm]; ///// int dp(int s, int a) { if(d[s][a] != -1) return d[s][a]; int& ans = d[s][a]; if(cnt[s][a] == 1) return ans = 0; ans = INF; for(int i = 0; i < m; i ++) { int f = 1<<i; if(!(s&f)) { int d1 = dp(s|f, a); int d2 = dp(s|f, a|f); ans = min(ans, max(d1, d2) + 1); } } return ans; } int main() { while(scanf("%d%d", &m, &n) && m) { char ch; memset(ft, 0, sizeof(ft)); memset(cnt, 0, sizeof(cnt)); memset(d, -1, sizeof(d)); for(int i = 0; i < n; i ++) { for(int j = 0; j < m; j ++) { do{ch = getchar();}while(!isalnum(ch)); ft[i] = ft[i] * 2 + ch - '0'; } } for(int s = 0; s <= (1<<m)-1; s ++) { //O(n*2^m) for(int i = 0; i < n; i ++) { int tmp = s & ft[i]; cnt[s][tmp] ++; } } printf("%d\n", dp(0,0)); //O(m*3^m) //Total: O(n*2^m + m*3^m) } return 0; }