# 題目: UVa 11420 - Chest of Drawers
# 題目說明
題目中的櫃子由數個抽屜堆疊而成，但是這種櫃子有安全上的疑慮
若你將一個抽屜完全抽出，那你能拿到下一層抽屜的東西
當前有L個抽屜，有S格是完全安全的，求總共有幾種排列法?
例如: L = 6, S = 4
則有6種可能
- U L L L L L
- L U L L L L
- L L U L L L
- L L L U L L
- L L L L U L
- L L L L U U
(L為上鎖的，U為未上鎖的，粗體為不安全)
INPUT:
每筆測資輸入兩個整數L、S，前者代表總抽屜數，後者代表安全的抽屜數
當L、S小於0時結束
OUTPUT:
輸出L個抽屜中有S個是安全的共有幾種排列法?
# 解題方法
先將所以可能的情況以動態規劃算出，再根據L及S的值查表輸出
先定義一個dp[i][j][k]
i為抽屜的數量j為有多少抽屜式安全的k分兩種情況，k = 0代表最上層的抽屜未上鎖，k = 1代表最上層抽屜上鎖
將dp[1][0][0]與dp[1][1][1]設為1
- 若只有1個抽屜時，0個抽屜是安全的，代表最上層為未上鎖的抽屜
- 若只有1個抽屜時，1個抽屜是安全的，代表最上層為上鎖的抽屜
若j = 0，則k不可能為1，所以只有1種情況，需分開處理
dp[i][0][0] = dp[i - 1][1][1] + dp[i - 1][0][0]
當從i - 1個抽屜新增一個未上鎖的抽屜時
- 若
k = 1只有最上層一個抽屜是安全時，新增一個未上鎖的抽屜會使原本安全的抽屜變不安全 - 若沒有抽屜是安全的，則新增一個未上鎖的抽屜不影響
以下為i與j均不為0的情況
dp[i][j][0]，也就是k = 0時，代表在最上層新增一個未上鎖的抽屜dp[i - 1][j + 1][1]此情況下在最上層新增一個未上鎖的抽屜，會導致原本安全的抽屜變不安全dp[i - 1][j][0]不影響其他抽屜
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;
}