題目： UVa - 11420 - Chest of Drawers

題目說明

d042. 11420 - Chest of Drawers - 高中生程式解題系統

Input： 每組測資有兩個整數，依序為 n、s，若皆小於 0 表結束。

Output： 輸出 n 個櫃子，確保剛好有 s 個櫃子是安全的所有情況數。

解題思路

動態規劃題，由於測資範圍不大，因此先算出所有情況的答案再輸出即可。

定義 dp[i][j][k]:

  • 若 k = 0，表有 i 個櫃子，j 個處於安全狀態，且最上層的櫃子沒有鎖。
  • 若 k = 1，表有 i 個櫃子，j 個處於安全狀態，且最上層的櫃子有鎖。

先設定初始狀態 dp[1][0][0] = 1，因為若只有一個櫃子，且櫃子是不安全的，表示只有最上層沒有鎖的這種可能，dp[1][1][1] = 1，因為若只有一個櫃子，且櫃子是安全的，表示只有最上層是有鎖的這種可能。

對於 dp[i][j][k]：

  • 若 k = 0，dp[i][j][0] = dp[i - 1][j + 1][1] + dp[i - 1][j][0]，
    1. dp[i - 1][j + 1][1]，表有 i - 1 個櫃子，剛好 j + 1 個是安全的，且最上層有鎖。
      可思考為在最上層加上一個沒鎖的櫃子，則原本的最上層會變得不安全，情況就變為 i 個櫃子，剛好 j 個是安全的，且最上層沒鎖。
    2. dp[i - 1][j][0]，表有 i - 1 個櫃子，剛好 j 個是安全的，且最上層沒鎖。
      可思考為在最上層加上一個沒鎖的櫃子，則確保安全的櫃子數量不變，情況就變為 i 個櫃子，剛好 j 個是安全的，且最上層沒鎖。
  • 若 k = 1，dp[i][j][1] = dp[i - 1][j - 1][1] + dp[i - 1][j - 1][0]，
    1. dp[i - 1][j - 1][1]，表有 i - 1 個櫃子，剛好 j - 1 個是安全的，且最上層有鎖。
      可思考為在最上層加上一個有鎖的櫃子，則會加入一個確定安全的櫃子，情況就變為 i 個櫃子，剛好 j 個是安全的，且最上層有鎖。
    2. dp[i - 1][j - 1][0]，可思考為在最上層加上一個有鎖的櫃子，則會加入一個確定安全的櫃子，情況就變為 i 個櫃子，剛好 j 個是安全的，且最上層有鎖。

簡單來說就是不斷枚舉加入最上層的櫃子，若 k = 0 表示加入的沒鎖，若 k = 1 表示加入的有鎖，找出對應的關係即可。

參考解法

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
#include <bits/stdc++.h>

using namespace std;

// reference: https://ppt.cc/fCBrlx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int n, s;
long long dp[67][67][2]; // dp[i][j][0] 表有 i 個櫃子，j 個處於安全狀態，且最上層的櫃子沒有鎖
                         // dp[i][j][1] 表有 i 個櫃子，j 個處於安全狀態，且最上層的櫃子有鎖

void compute()
{
    dp[1][0][0] = 1;
    dp[1][1][1] = 1;

    for (int i = 2; i < 66; ++i)
    {
        // 只有一個安全且最上層有鎖 -> 加一層沒鎖
        // 沒有任何安全且最上層沒鎖 -> 加一層沒鎖
        dp[i][0][0] = dp[i - 1][1][1] + dp[i - 1][0][0];
        for (int j = 1; j <= i; ++j)
        {
            // 加一層沒鎖
            dp[i][j][0] = dp[i - 1][j + 1][1] + dp[i - 1][j][0];
            // 加一層有鎖
            dp[i][j][1] = dp[i - 1][j - 1][1] + dp[i - 1][j - 1][0];
        }
    }
}

int main()
{
    compute();
    while (cin >> n >> s && !(n < 0 && s < 0))
        cout << dp[n][s][0] + dp[n][s][1] << '\n';
}

參考資料

d042. 11420 - Chest of Drawers - 高中生程式解題系統
UVa 11420 - Chest of Drawers | NaiveRed’s Blog