24h購物| | PChome| 登入
2011-06-11 08:13:37| 人氣3,632| 回應6 | 上一篇 | 下一篇

d887. 1.山脈種類(chain)

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

內容 :

輸入說明 :

每行有1個數字N(2<=N<=25)

輸出說明 :

請輸出一個整數,表示總步數為2N的山脈共有多少種。

範例輸入 :

34

範例輸出 :

514

提示 :

(1)測資有誤請告知感謝

(2)另外兩題本人都只過了局部測資

請會的人幫忙出吧

出處 :

99北市賽 (管理:leopan0922)



作法 : DP
上山的個數,在過程中,必然大於等於下山的個數
設上山個數A,下山個數B,則A >= B
   我們可以將A看成下圖的往右,B看成往上
最後得到所有路徑必須在紅線下,等效於求左下點到右上點的最短路徑
同時不超過紅線的 DP








/**********************************************************************************/
/*  Problem: d887 "1.山脈種類(chain)" from 99北市賽                        */
/*  Language: C                                                                   */
/*  Result: AC (6ms, 278KB) on ZeroJudge                                          */
/*  Author: morris1028 at 2011-06-11 07:57:36                                     */
/**********************************************************************************/


#include<stdio.h>
main() {
    int n, a, b;
    while(scanf("%d", &n) == 1) {
        long long DP[27][27] = {0};
        DP[0][1] = 1;
        for(a = 1; a <= n + 1; a++)
            for(b = a; b <= n+1; b++)
                DP[a][b] = DP[a-1][b] + DP[a][b-1];
        printf("%lld\n", DP[n+1][n+1]);
    }
    return 0;
}

台長: Morris
人氣(3,632) | 回應(6)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:d907. 3. 城市走法計數
此分類上一篇:d547. 4. 秘密(secrets)

Lee
數學好真吃香
2011-06-29 00:03:15
版主回應
網路上有提供另外一種的版本,沒看懂
2011-06-29 08:22:06
K
檔案上測試輸入18
他的輸出是477638700
為什麼你的輸入範例34才只有514
2011-10-06 12:26:20
K
抱歉 剛還沒跑過程式就先回應
2011-10-06 12:36:55
哈樓
想問"網路上有提供另外一種的版本"是哪種
我怎麼找都只找到你的=口=
2011-11-05 11:10:40
版主回應
https://sites.google.com/a/hpsh.co.cc/code/ti-mu/d887-1chain
2011-11-05 15:51:43
Tim
2015-01-25 18:30:53
Tim
這是我找到另一個不錯的想法
2015-01-25 18:32:03
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文