UVa11420 - Chest of Drawers(動態規劃)

題目大意

抽屜櫃是很方便的家具之一，可以放入很多的物品，而且每一個抽屜都可以選擇上鎖或不上鎖，上鎖的抽屜就會相當安全，但要小心，如果 i 抽屜上鎖，i+1抽屜不上鎖，那麼小偷可以透過 i+1 抽屜抽掉後，把 i 的抽屜物品拿走。

我們想請問如果我們給你一個抽屜櫃並且有 n 個抽屜，並要保證 s 個物品安全，想請問一共有幾種做法？
UVa 題目中的 U 表示不上鎖，L 表示上鎖，在 n=6, s=4 的情況下，有六種做法。

題目連結

重點觀念

• 察覺這是一個 3 維 DP
• 理解題目的抽屜，有點不好懂XD
• 透過 DP 來解決各種發生狀態
  • 如果上一層沒鎖，這層有鎖，那要怎麼用 DP 解決。
  • 有可能鎖著的櫃子，比櫃子數量來的更多嗎?

分析

• 首先我們可以確定一定有兩個變數
  • 幾個抽屜、有幾個上鎖
  • 但好像沒有辦法解決，透過 i+1 抽屜抽掉後，把 i 的抽屜物品拿走。這種可能性？
  • 那我們可以試試一種方法來解決這種問題。
  • 增加一個抽屜，都是放到櫃子中的最上層，我們每次都只判斷最上層的櫃子有沒有鎖；如此一來，就解決中間櫃子有沒有鎖的問題，因為中間的櫃子一定都是透過其他的櫃子累加上來的。
• 因此我們就再增加一個變數，最上層的櫃子有沒有鎖？
• dp[i][j][k]
  • i 是抽屜
  • j 是物品可置放在安全抽屜的個數，簡稱可靠抽屜
    注意：可靠抽屜並不是鎖，但有可靠抽屜才會有鎖
  • k 是最上層有沒有上鎖，1 表示有、0 表示沒有。
• 那就準備進行 DP 規劃拉，我們來看看 DP 的狀態轉移
  • 先找出最初的設定值
    • dp[1][0][0] = 1，在 1 個櫃子、0 個可靠抽屜的情況下有一種做法，合理！
      0 個櫃子、0 個可靠抽屜，則不合理。這樣並不符合題目要求。
    • dp[1][1][1] = 1，1 個櫃子、1 個可靠抽屜的情況下只有一種作法，合理！
      • 0 個櫃子、1 個可靠抽屜，則不合哩，你沒有櫃子，可靠抽屜有甚麼用阿XD。
      • dp[1][0][1] = 1，1 個櫃子、0 個可靠抽屜的情況下最上層的櫃子是所住的，不合理！
        這裡就是一個很明顯的範例點，由於 n=1 因此最上層就是其本身，但是沒有鎖怎麼會有可靠抽屜呢，因此這是很明顯的錯誤
  • 得出結論，抽屜的數量必須要大於鎖的數量
  • 狀態轉移公式
    • dp[i][0][0] = dp[i-1][0][0] + dp[i-1][1][1]
      • 需要特別注意，可能有些人會搞不懂為甚麼這裡也要加 dp[i-1][1][1]
        因為在 dp[i][0][0] 情況下，最上層的櫃子是沒有鎖的，此時 dp[i-1][1][1] 則是有鎖，但現在最上層加了一層沒鎖的抽屜，那第二層有鎖也是白鎖。
      • 因此我們的可靠抽屜必須 -1
    • dp[i][j][0] = dp[i-1][j+1][1] + dp[i-1][j][0]
      • 由於 dp[i][j][0] 最上層沒有鎖，因此 dp[i-1][j+1][1] 中安全抽屜會少一(最上層的抽屜有鎖住，勢必可靠抽屜會多一個)，會被人從最上層抽屜拿取上鎖的抽屜。
      • dp[i-1][j][0] 則很合理
    • dp[i][j][1] = dp[i-1][j-1][0] + dp[i-1][j-1][1]
      • dp[i-1][j-1][0] 很合理，現在最上層有鎖，因此安全抽屜會加一
      • dp[i-1][j-1][1]，同上

參考連結

UVa 11420 - Chest of Drawers by pinghenotes

心得

我記得我好像高中，就有寫過這題了XD，而且我印象我想了一個禮拜才寫出這題R….，那時候的我好笨QQ，不過那時候我記得網路上還沒有太多詳解，因此我沒有辦法順利解決這些題目。

現在有了，也讓我學會了！太開心了，趕緊記錄起來

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 70
using namespace std;
int dp[MAXN][MAXN][2];
int n, s;

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    dp[1][0][0] = 1; //註解 4-1-1
    dp[1][1][1] = 1; //註解 4-1-2 
    for(int i = 2; i < MAXN-2; i++){
        dp[i][0][0] = dp[i-1][0][0] + dp[i-1][1][1]; //註解 4-3-1
        for(int j = 1; j <= i; j++){
            dp[i][j][0] = dp[i-1][j+1][1] + dp[i-1][j][0]; //註解 4-3-2
            dp[i][j][1] = dp[i-1][j-1][0] + dp[i-1][j-1][1]; //註解 4-3-3
        }
    }
 
    while(cin >> n >> s && n >= 0 && s >= 0){
        cout << dp[n][s][0] + dp[n][s][1] << "\n"; //輸出答案
    }
    return 0;
}