百搭背心★瘋搶↘120工程師靠存股年領百萬股息吉隆坡最便宜行程一覽表不捨學生找「槌」 高中...
2011-09-04 19:55:30 人氣(619) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

d042. 11420 - Chest of Drawers

0
收藏
0
推薦

d042. 11420 - Chest of Drawers

內容 :


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

一個 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

出處 :

UVa ACM 11420 (管理:snail)



作法 : DP

DP[櫃子總數][安全櫃子總數][最後一個是 U 還是 L]

接下來的遞迴部分, 請參考下面, 不多作說明了

/**********************************************************************************/
/*  Problem: d042 "11420 - Chest of Drawers" from UVa ACM 11420                   */
/*  Language: C                                                                   */
/*  Result: AC (0ms, 302KB) on ZeroJudge                                          */
/*  Author: morris1028 at 2011-09-04 19:42:59                                     */
/**********************************************************************************/


#include<stdio.h>
main() {
    int n, s, i, j;
    long long DP[70][70][2] = {};/*[total][safe][U(0) or L(1)]*/
    DP[1][1][1] = 1, DP[1][0][0] = 1;
    for(i = 1; i <= 64; i++) {
        for(j = 0; j <= i; j++) {
            DP[i+1][j+1][1] += DP[i][j][1];/*LL*/
            DP[i+1][j][0] += DP[i][j][0] + DP[i][j][1];/*UU LU*/
            DP[i+1][j][1] += DP[i][j][0];/*UL*/
        }
    }
    while(scanf("%d %d", &n, &s) == 2) {
        if(n < 0 && s < 0)    break;
        printf("%lld\n", DP[n][s][0] + DP[n][s][1]);
    }
    return 0;
}

d04211420Chest of Drawers
台長:Morris
人氣(619) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:d087. 107 - The Cat in the Hat
此分類上一篇:d285. 727 Postfix Expression

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文