Morris' Blog

2011-06-11 08:13:37Morris

d887. 1.山脈種類(chain)

留言 6 收藏 0 推薦 0

內容：

輸入說明：

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

輸出說明：

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

範例輸入：

範例輸出：

提示：

(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;
}

上一篇：d547. 4. 秘密(secrets)

下一篇：d907. 3. 城市走法計數