d042: 11420 - Chest of Drawers
標籤 :
通過比率 : 96% (110 人 / 115 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-02-04 22:00

內容



1: 斗櫃

斗櫃就是如左圖由很多抽屜垂直排列組成的櫃子。雖然這是個很有用的家具,但是如果要鎖這些抽屜時卻發生了問題——抽屜即使上鎖了也不一定安全。例如假設從上面往下數第三個抽屜鎖上了,但是它上面的那個抽屜卻沒鎖。這時鎖起來的抽屜也不安全,因為只要把它上面的抽屜整個拉出來就可拿到裡面的東西了。 

一個 n 個抽屜的斗櫃,會有數個方式來確保剛好有 s 個抽屜是安全的。以左圖的斗櫃為例,有六個方式可以確保剛好四個抽屜是安全的。這六個方式如圖 2 所示。 

給你 n s 的值,請你算有多少個方式可以確保它們的安全。 

 

  

 

 

 2: 圖中的 L 表示那個抽屜是鎖著的,則表示沒上鎖。這就是可以確保剛好 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
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
提示 :

DP

感谢morris1028补上图片!

標籤:
出處:
UVa11420 [編輯:
snail (蝸牛)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」