UVA Mega Man's Mission（状压dp）

把消灭了那些机器人作为状态S，预处理出状态S下可以消灭的机器人，转移统计方案。方案数最多16!，要用64bit保存方案。

#include<bits/stdc++.h>
using namespace std;

const int Mx = 16, maxs = 1<<16;
int a[Mx];//arm
typedef long long ll;
ll meo[maxs];
int vis[maxs] ,clk;
int canAtk[maxs];
int n;

ll dp(int S)
{
    if(vis[S] == clk) return meo[S];
    vis[S] = clk;
    meo[S] = 0;
    for(int i = 0; i < n; i++){
        if(S>>i&1) continue;
        if(canAtk[S]>>i&1) meo[S] += dp(S|1<<i);
    }
    return meo[S];
}

int read(){ int x; scanf("%1d",&x); return x; }
int IN()
{
    int re = 0;
    for(int i = 0; i < n; i++){
        re |= read()<<i;
    }
    return re;
}

//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
/*
    int ce = 1;
    for(int i = 1; i <= 16; i++){
        ce *= i;
        cout<<ce<<endl;
    }
*/
    int T; cin>>T;
    while(T--){
        scanf("%d",&n);
        canAtk[0] = IN();
        for(int i = 0; i < n; i++){
            a[i] = IN();
        }
        int mxs = (1<<n)-1;
        for(int S = 1; S <= mxs; S++){
            canAtk[S] = canAtk[0];
            for(int i = 0; i < n; i++)if(S>>i&1){
                canAtk[S] |= a[i];
            }
        }
        meo[mxs] = 1; vis[mxs] = ++clk;
        printf("Case %d: %lld
",clk,dp(0));
    }
    return 0;
}