UVa11795 - Mega Man's Mission（狀壓dp）

題目連結

簡介：

每個怪物需要特定的武器擊敗，每消滅一個怪物将會得到ta的武器

計算可以消滅所有怪物的序列總數

分析：

狀壓dp

monster[i]：打倒的怪物的狀态為i時，獲得的武器可以打倒的怪物

arms[i]：擁有的武器為i時，可以打倒的怪物

f[i]：打倒的怪物的狀态為i時，可能的方案數

arms數組就是輸入資料轉化為二進制數

在轉移的的時候，枚舉下一個打倒的怪物

tip

開ll

#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long

using namespace std;

const int N=;
int er[]={,,,,,,,,,,,,,,,,,};      
//這裡并不是2^i，而是2^(i-1),這樣就可以和1~n的怪物對應起來了，第i個怪物對應的就是er[i]
int n;
int arms[N],monster[N];
ll f[N];

void doit()
{
    int i,j,k;
    f[]=;
    for (i=;i<(<<n)-;i++)
    {
        if (!f[i]) continue;

        k=monster[i];                         //下一步可以打倒的怪物 
        for (j=;j<=n;j++)
            if ((k&er[j])!=&&(i&er[j])==)   //枚舉下一個打倒的怪物 
                f[i|er[j]]+=f[i];
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    for (int cas=;cas<=T;cas++)
    {
        memset(arms,,sizeof(arms));
        memset(monster,,sizeof(monster));
        memset(f,,sizeof(f));

        scanf("%d",&n);
        char s[];

        scanf("%s",&s);
        int k=;
        for (int i=;i<n;i++)
            if (s[i]=='1') k+=er[i+];
        arms[]=k; monster[]=k;           //擁有第0件武器 

        for (int i=;i<=n;i++)
        {
            scanf("%s",&s);
            int k=;
            for (int j=;j<n;j++)
                if (s[j]=='1') k+=er[j+];
            arms[er[i]]=k;
        }

        for (int i=;i<(<<n);i++)       //打倒怪物k之後就可以獲得武器k 
        {
            int k=monster[];
            for (int j=;j<=n;j++)
                if (i&er[j]) k|=arms[er[j]];
            monster[i]=k;
        }

        doit();

        printf("Case %d: %lld\n",cas,f[(<<n)-]);
    }
    return ;
}