24h購物| | PChome| 登入
2011-06-07 17:33:35| 人氣1,563| 回應0 | 上一篇 | 下一篇

d810. 大朋友下樓梯

推薦 0 收藏 0 轉貼0 訂閱站台

http://zerojudge.tw/ShowProblem?problemid=d810

內容 :

傳說,有個遊戲叫做大朋友下樓梯,這個遊戲有三種難度,簡單中等困難。

三種難度的差別是,簡單的難度大朋友一次只能下樓梯 1格

中等的是則是,大朋友一次可以下樓梯 1格或 2格

困難的比較具有挑戰性,大朋友一次可以下 1格、 2格或 3格


現在我們想知道,大朋友有幾種下樓梯的方法可以走到地下k樓

對了,有一個限制是,大朋友不能上樓梯只能下樓梯

輸入說明 :

給定兩個正整數 t, k , t代表遊戲難度,值為1~3 分別代表,簡單中等困難。

k則是一個負數,代表地下k樓(0>k>-20)

包含多筆測試資料。

輸出說明 :

輸出大朋友走到地下K層後的方法數。

範例輸入 :

1 -1
1 -2
2 -1
2 -2
2 -3
2 -4
3 -1
3 -2
3 -3

範例輸出 :

1
1
1
2
3
5
1
2
4

提示 :

出處 :

(管理:shik)

作法 : 數學
一個是費氏數列,另一個是 an = an-1 + an-2 + an-3

/**********************************************************************************/
/*  Problem: d810 "大朋友下樓梯" from                                       */
/*  Language: C                                                                   */
/*  Result: AC (4ms, 260KB) on ZeroJudge                                          */
/*  Author: morris1028 at 2011-06-02 22:40:47                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
main() {
    int a, b, c;
    int DP[4][20] = {};
    DP[1][1] = 1, DP[2][0] = 1, DP[2][1] = 1, DP[3][0] = 1, DP[3][1] = 1;
    for(a = 1; a < 4; a++)
        for(b = 2; b < 20; b++)
            for(c = 1; c <= a && b-c >= 0; c++)
                DP[a][b] += DP[a][b-c];
    while(scanf("%d %d", &a, &b) == 2)
        printf("%d\n", DP[a][abs(b)]);
    return 0;
}

台長: Morris
人氣(1,563) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:d815. 水火不容II
此分類上一篇:d809. 黑暗土地

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文