Problem Solving►UVa

UVa 11795 - Mega Man's Mission

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

洛克人，本身就帶了把武器，可以打倒相對應的機器人。而打倒機器人後，可獲得他們的武器。每把武器有其所能對付的機器人。
問有幾種方法可擊倒全部的機器人。

Solution

覺得題目很有趣就開來寫，結果一整天就消失了，平常幾乎沒啥在用位運算，也沒寫過狀態壓縮 DP，心已打烊…

好不容易讀懂別人的 code 後才開始著手寫，如果看不太懂，可以把過程中的變數二進位寫下來，一一記錄其變化，或許能幫助理解。

首先要做的是先把每個武器所能打倒的敵人，以二進位的方式存下，編號小的存在 LSB ，方便待會運算。 

int r = 1;
for (j = 0; j < n; j++)
{
    if (str[j] == '1')
        robot[i] |= r;
        r <<= 1;
}

如果輸入是 01101 ， 就會存成 10110。(二進位)

dp[N] 是當前集合的次數，有點像 coin change 問幾種組合方式一樣。
state[N] 是當前能擊敗的集合，也就是它存的二進位代表能擊倒的敵人。

初始化一開始的狀態和次數。

state[0] = robot[0];
dp[0] = 1;

而我們要去跑所有的狀態，也就是今天 n = 3 的話，全部的組合就為 $2^3$ (000,001,010,011,100,101,110,111)，all = 1 << n。

for (i = 0; i < all; i++) 外層的迴圈，
i 所跑得為當前已擊倒的敵人集合(以二進位存)，ex. i = 4 = 100 表示這是已擊倒第 3 個機器人的集合。
(用詞上 擊倒 跟 走過 一樣)

每次我們會判斷當前 需要擊倒 且 可以擊倒 的 ，ok = (~i)&state[i] 。舉例來說: 

i = 100 => 已擊倒第 3 個機器人的集合
~i = 011 => 還需擊倒第 1 和 2 的機器人 
state[i] = 110 => 在 i 這個狀態時，我們能擊倒 2 和 3 的機器人

(~i)&state[i] = 010 => 我們需要且可以的為 第 2 個

接著就是選擇要擊倒哪個機器人了，r 為機器人，ok&r 則為前面篩選過後可以的。

int r = 1;
for (j = 1; j <= n; j++)
{
    if (ok&r)
    {
        dp[r | i] += dp[i];
        state[r | i] = state[i] | robot[j];
    }

    r <<= 1;//換下一個
}

舉例說明:

i = 100 => 已擊倒第 3 個
r = 010 => 選擇第 2 個
r | i = 110 => 擊倒完第 2 個機器人後的集合

其 state[r|i] 自然就是 原本 的加上(or) 擊倒第二個後所獲得之武器能對付的 ， state[i] | robot[j] 。

最後所要求的集合是已全部擊倒的，就是 1111… ，其次數: dp[all - 1] 。

以上說明完畢，還不太熟，如果有錯誤的地方還請指出 QQ。

Code

UVa 11795UVa 11795 - Mega Man's Mission
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<algorithm>
#define N 1<<16
using namespace std;

int main()
{
    long long dp[N];//當前集合的次數
    int state[N];//當前能擊敗的集合
    int Case;
    char str[17];

    scanf("%d", &Case);

    for (int c = 1; c <= Case; c++)
    {
        int n, i, j;
        int robot[17] = {};//0 為 mega buster,其餘為擊敗此 robot[] 後，可以打倒的其他 robot 集合

        scanf("%d", &n);
        getchar();
        fill(state, state + (1 << n), 0);
        fill(dp, dp + (1 << n), 0);

        for (i = 0; i <= n; i++)
        {
            gets(str);
            //讓第一個存在 LSB
            int r = 1;
            for (j = 0; j < n; j++)
            {
                if (str[j] == '1')
                    robot[i] |= r;
                r <<= 1;
            }
        }

        //init
        state[0] = robot[0];
        dp[0] = 1;

        int all = 1 << n;//全部的組合
        for (i = 0; i < all; i++)
        {
            /*
            i = 為當前已走的(集合)
            ~i = 則為還沒走的
            state[i] = 當前集合可以走的
            */
            int ok = (~i)&state[i];//未走且可走的
            
            //選擇要擊倒哪個
            int r = 1;
            for (j = 1; j <= n; j++)
            {
                if (ok&r)
                {
                    dp[r | i] += dp[i];//次數計算
                    //擊倒完後的 state 集合 ，變成 "未擊倒前的" 加上(or) "擊倒後才可以的"
                    state[r | i] = state[i] | robot[j];
                }

                r <<= 1;//換下一個
            }
        }

        printf("Case %d: %lld\n", c, dp[all - 1]);
    }

    return 0;
}