Embedded Files
出處
http://zerojudge.tw/ShowProblem?problemid=d042
內容 ：
斗櫃就是如左圖由很多抽屜垂直排列組成的櫃子。雖然這是個很有用的家具，但是如果要鎖這些抽屜時卻發生了問題——抽屜即使上鎖了也不一定安全。例如假設從上面往下數第三個抽屜鎖上了，但是它上面的那個抽屜卻沒鎖。這時鎖起來的抽屜也不安全，因為只要把它上面的抽屜整個拉出來就可拿到裡面的東西了。
一個 n 個抽屜的斗櫃，會有數個方式來確保剛好有 s 個抽屜是安全的。以左圖的斗櫃為例，有六個方式可以確保剛好四個抽屜是安全的。這六個方式如圖 2 所示。
給你 n 和 s 的值，請你算有多少個方式可以確保它們的安全。
圖 2: 圖中的 L 表示那個抽屜是鎖著的，U 則表示沒上鎖。這就是可以確保剛好 4 個抽屜是安全的的六個組合。安全的抽屜以粗體字母來表示。
輸入說明 ：
輸入檔最多有 5000 行的輸入。
每行有兩個整數 n 及 s (1 ≤ n ≤ 65 且 0 ≤ s ≤ 65)。其中 n 是共有幾個抽屜，s 是要確保安全的抽屜數量。
輸入以含有兩個負數的一行作為結束。請不要處理這行輸入。
輸出說明 ：
相對於每行的輸入要產生一行輸出。這行要含有一個表示有幾個方法可以確保 n 個抽屜中剛好有 s 個抽屜是安全的。
範例輸入 ：
6 2
6 3
6 4
-1 -1
範例輸出 ：
16
9
6
提示 ：
DP
感谢morris1028补上图片！
出處 ：
UVa ACM 11420 (管理：snail)
解題策略
使用DP，
有i個櫃子，確定j個櫃子是安全的，且最上一層是上鎖的，
加上有i-1個櫃子，確定j-1個櫃子是安全的，且最上一層是上鎖的，
加上有i-1個櫃子，確定j-1個櫃子是安全的，且最上一層是沒有鎖的，
num[i][j][1]+=num[i-1][j-1][0]+num[i-1][j-1][1];
有i個櫃子，確定j個櫃子是安全的，且最上一層是沒有鎖的，
加上有i-1個櫃子，確定j+1個櫃子是安全的，且最上一層是上鎖的，
加上有i-1個櫃子，確定j個櫃子是安全的，且最上一層是沒有鎖的，
num[i][j][0]+=num[i-1][j+1][1]+num[i-1][j][0];
Page updated
Google Sites
Report abuse