HDU/HDOJ 2067 小兔的棋盘 DP/卡特兰数

HDU/HDOJ 2067 小兔的棋盘

小兔的棋盘

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12782    Accepted Submission(s): 6392
 

Problem Description

小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!

Input

每次输入一个数n(1<=n<=35)，当n等于－1时结束输入。

Output

对于每个输入数据输出路径数，具体格式看Sample。

Sample Input

1

3

12

-1

Sample Output

1 1 2

2 3 10

3 12 416024

Author

Rabbit

Source

​​RPG专场练习赛 ​​

Recommend

Lcy

算法分析：

简单DP，打表做就行,打一半就ok。

递归方程：dp[i][j]=dp[i-1][j]+dp[i][j-1]

初始化：dp[1~40][0]=1

卡特兰数也能实现

代码实现：

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cctype>  
#include<cmath>  
#include<iostream>  
#include<sstream>  
#include<iterator>  
#include<algorithm>  
#include<string>  
#include<vector>  
#include<set>  
#include<map>  
#include<stack>  
#include<deque>  
#include<queue>  
#include<list> 
using namespace std;
typedef long long ll; 
int n; ll dp[41][41];
int DP()    //只需要计算下半三角形
{

    for(int i=0;i<=40;i++)
        dp[i][0]=1;
    for(int i=1;i<=40;i++)
        for(int j=1;j<=i;j++)
    {
        //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
        dp[i][j]=dp[i-1][j]+dp[i][j-1];
    }
}
int main()
{
     int t=0;
     DP();
     /*for(int i=0;i<=10;i++)
        {for(int j=0;j<=10;j++)
     {
        cout<<dp[i][j]<<" ";
     }
     cout<<endl;
        }
        */
     while(scanf("%d",&n)!=EOF)
     {   
          if(n==-1) break;
         t++;
         printf("%d %d %lld",t,n,2*dp[n][n]);
         cout<<endl;
     }
    return 0;
}

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cctype>  
#include<cmath>  
#include<iostream>  
#include<sstream>  
#include<iterator>  
#include<algorithm>  
#include<string>  
#include<vector>  
#include<set>  
#include<map>  
#include<stack>  
#include<deque>  
#include<queue>  
#include<list> 
using namespace std;
typedef long long ll;
int main()
{
  ll Catalan[40] = {0};
  Catalan[0] = 1;
  Catalan[1] = 1;
  for (int i = 2 ; i <= 35 ; i++)
    for (int j = 0 ; j <= i - 1 ; j++)
      Catalan[i] += Catalan[j] * Catalan[i - 1 - j];
  int num = 1;
  int n;
  while (~scanf ("%d",&n) && n != -1)
    printf ("%d %d %lld\n",num++,n,Catalan[n] * 2);
  return 0;
}