# 題目: UVa 11420 - Chest of Drawers

# 題目說明

題目中的櫃子由數個抽屜堆疊而成，但是這種櫃子有安全上的疑慮
若你將一個抽屜完全抽出，那你能拿到下一層抽屜的東西
當前有 L 個抽屜，有 S 格是完全安全的，求總共有幾種排列法？

例如: L = 6, S = 4
則有 6 種可能

1. U L L L L L
2. L U L L L L
3. L L U L L L
4. L L L U L L
5. L L L L U L
6. L L L L U U
   ( L 為上鎖的， U 為未上鎖的，粗體為不安全)

INPUT:
每筆測資輸入兩個整數 L 、 S ，前者代表總抽屜數，後者代表安全的抽屜數
當 L 、 S 小於 0 時結束

OUTPUT:
輸出 L 個抽屜中有 S 個是安全的共有幾種排列法？

# 解題方法

先將所以可能的情況以動態規劃算出，再根據 L 及 S 的值查表輸出

先定義一個 dp[i][j][k]

1. i 為抽屜的數量
2. j 為有多少抽屜式安全的
3. k 分兩種情況， k = 0 代表最上層的抽屜未上鎖， k = 1 代表最上層抽屜上鎖

將 dp[1][0][0] 與 dp[1][1][1] 設為 1

1. 若只有 1 個抽屜時，0 個抽屜是安全的，代表最上層為未上鎖的抽屜
2. 若只有 1 個抽屜時，1 個抽屜是安全的，代表最上層為上鎖的抽屜

若 j = 0 ，則 k 不可能為 1，所以只有 1 種情況，需分開處理
dp[i][0][0] = dp[i - 1][1][1] + dp[i - 1][0][0]
當從 i - 1 個抽屜新增一個未上鎖的抽屜時

1. 若 k = 1 只有最上層一個抽屜是安全時，新增一個未上鎖的抽屜會使原本安全的抽屜變不安全
2. 若沒有抽屜是安全的，則新增一個未上鎖的抽屜不影響

以下為 i 與 j 均不為 0 的情況

1. dp[i][j][0] ，也就是 k = 0 時，代表在最上層新增一個未上鎖的抽屜
   • dp[i - 1][j + 1][1] 此情況下在最上層新增一個未上鎖的抽屜，會導致原本安全的抽屜變不安全
   • dp[i - 1][j][0] 不影響其他抽屜
2. dp[i][j][1] ，也就是 k = 1 時，代表在最上層新增一個上鎖的抽屜
   • dp[i - 1][j - 1][1] 直接新增一個安全的抽屜，不影響其他抽屜
   • dp[i - 1][j - 1][0] 同上

# 參考程式碼

#include <iostream>

using namespace std;

long long dp[67][67][2];

int N, S;

int main()

{

	// fast io

	ios::sync_with_stdio(false);

	cin.tie(nullptr);

	cout.tie(nullptr);

	// if there is one drawer, and no safe drawers, the top drawer must be unlock

	// if there is one drawer, and exist one safe drawer, the top drawer must be lock

	dp[1][0][0] = 1;

	dp[1][1][1] = 1;

	for (int i = 2; i < 66; ++i)

	{

		// if there is i drawers, and no safe drawers =

		// there is (i - 1) drawers, the top one is the only lock drawer +

		// there is (i - 1) drawers, no drawer is safe

		dp[i][0][0] = dp[i - 1][1][1] + dp[i - 1][0][0];

		for (int j = 1; j <= i; ++j)

		{

			// add one unlock drawer

			// if the top drawer is lock, this will lead to it unsafe

			dp[i][j][0] = dp[i - 1][j + 1][1] + dp[i - 1][j][0];

			// add one lock drawer

			dp[i][j][1] = dp[i - 1][j - 1][1] + dp[i - 1][j - 1][0];

		}

	}

	while (cin >> N >> S, N >= 0 && S >= 0) cout << dp[N][S][0] + dp[N][S][1] << "\n";

	return 0;

}

# 參考資料

https://www.larrysprognotes.com/UVa-11420/