UVA-1252 Twenty Questions(状態圧縮&記憶化探索)

タイトルリンク:UVA-1252 Twenty Questions
に言及
n(0)
構想
mのデータ範囲や題意から,状態圧縮が容易に考えられ,集合をバイナリビットで表す.dp(i,j)=c iは、質問された特徴を表す集合jは、私が選択した物体が有する特徴を決定した集合を表すほど明らかであり、jはiのサブセットに違いない.c現在の状態について質問する回数を示す

dp(i, j) = 1 + min(max(dp(i|(1<<k), j|(1<<k)),  dp(i|(1<<k), j))) k         。

maxの2つは、私が持っている特徴|私が持っている不快感|私が持っている特徴です.100%確実であることを保証するため、最悪の場合の最良の場合を選択します.これはmaxを使う理由です.(jのすべての特徴を満たし、iがjを除く他の特徴を満たさない)に合致する物体が1個以下である場合、結果を決定できるため、質問を停止することができる.このカウントプロセスを前処理して効率を向上させることができる.状態が重複しすぎるので、記憶化検索に使用します.
コード#コード#

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <map>

using namespace std;

#define LL long long

const int MOD = 1000000007;
const int N = 200;
const int M = 12;
int cnt[1<<M][1<<M];
int p[N];
int dp[1<<M][1<<M];

void init(int n, int m)
{
    for(int s=0; s<(1<<m); s++)
        for(int i=0; i<n; i++)
            cnt[s][p[i]&s]++;
}

int dfs(int s, int a, int m)
{
    if(dp[s][a] != 0x3f3f3f3f)
        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(dfs(s|(1<<i),a,m), dfs(s|(1<<i),a|(1<<i),m)));
    }
    return dp[s][a]+=1;
}

int main()
{
    int n, m;
    char t[12];
    while(~scanf("%d%d", &m, &n) && m && n)
    {
        memset(cnt, 0, sizeof(cnt));
        memset(dp, 0x3f, sizeof(dp));
        for(int i=0; i<n; i++)
        {
            scanf("%s", t);
            p[i] = 0;
            for(int j=0; j<m; j++)
                if(t[j] == '1')
                    p[i] |= 1<<j;
        }
        init(n, m);
        printf("%d
", dfs(0, 0, m));
    }
}