2011-06-11 08:13:37Morris
d887. 1.山脈種類(chain)
內容 ：
輸入說明 ：
每行有1個數字N(2<=N<=25)
輸出說明 ：
請輸出一個整數，表示總步數為2N的山脈共有多少種。
範例輸入 ：
34
範例輸出 ：
514
提示 ：
(1)測資有誤請告知感謝
(2)另外兩題本人都只過了局部測資
請會的人幫忙出吧
出處 ：
99北市賽 (管理：leopan0922)
作法 : DP
上山的個數，在過程中，必然大於等於下山的個數
設上山個數A，下山個數B，則A >= B
我們可以將A看成下圖的往右，B看成往上
最後得到所有路徑必須在紅線下，等效於求左下點到右上點的最短路徑
同時不超過紅線的 DP
作法 : 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;
}
下一篇：d907. 3. 城市走法計數
你的解釋很好懂，謝謝參考
http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=feeec416b290b5cad22f36f09121037cbf3f9d44c (標題:卡特蘭數)
想問"網路上有提供另外一種的版本"是哪種
我怎麼找都只找到你的=口=
版主回應
https://sites.google.com/a/hpsh.co.cc/code/ti-mu/d887-1chain
2011-11-05 15:51:43
這是我找到另一個不錯的想法