首页 > 代码库 > hdu2067 小兔的棋盘 DP/数学/卡特兰数

hdu2067 小兔的棋盘 DP/数学/卡特兰数

棋盘的一角走到另一角并且不越过对角线,卡特兰数,数据量小,可以当做dp求路径数

技术分享
 1 #include<stdio.h>
 2 long long a[36][36];
 3 int main()
 4 {
 5     int n,count=0;
 6     while (scanf("%d",&n)!=EOF&&n!=-1)
 7     {
 8         int i,j;
 9         long long s;
10         count++;
11         for (i=1;i<=n;i++) a[0][i]=1;
12         for (i=1;i<n;i++)
13         {
14             a[i][i]=a[i-1][i];
15             for (j=i+1;j<=n;j++) a[i][j]=a[i][j-1]+a[i-1][j];
16         }
17         s=a[n-1][n]*2;
18         printf("%d %d %I64d\n",count,n,s);
19     }
20     return 0;
21 }
View Code

 

hdu2067 小兔的棋盘 DP/数学/卡特兰数