小兔的棋盤

Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12359????Accepted Submission(s): 6184


Problem Description 小兔的叔叔從外面旅游回來給她帶來了一個禮物，小兔高興地跑回自己的房間，拆開一看是一個棋盤，小兔有所失望。不過沒過幾天發(fā)現(xiàn)了棋盤的好玩之處。從起點(diǎn)(0，0)走到終點(diǎn)(n,n)的最短路徑數(shù)是C(2n,n),現(xiàn)在小兔又想如果不穿越對角線(但可接觸對角線上的格點(diǎn))，這樣的路徑數(shù)有多少?小兔想了很長時間都沒想出來，現(xiàn)在想請你幫助小兔解決這個問題，對于你來說應(yīng)該不難吧!
Input 每次輸入一個數(shù)n(1<=n<=35)，當(dāng)n等于－1時結(jié)束輸入。
Output 對于每個輸入數(shù)據(jù)輸出路徑數(shù)，具體格式看Sample。
Sample Input 1312-1
Sample Output 1 1 22 3 103 12 416024

解析：卡特蘭數(shù)的典型應(yīng)用。

代碼：

#include<iostream> #include<cmath> #include<string> #include<string.h> #include<map> #include<stdio.h> #include<algorithm> using namespace std; __int64 kta[36]; int main() { kta[0]=kta[1]=1; int i,j; __int64 sum=0;for( i=2;i<=35;i++) { sum=0; for( j=0;j<i;j++) { sum+=(kta[j]*kta[i-j-1]); }kta[i]=sum; } int n; int flag=1; while(cin>>n) {if(n==-1)break; printf("%d %d %I64d\n",flag,n,kta[n]*2); flag++; } return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu-2067的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。