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

本文主要是介绍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;
}

 

这篇关于HDU/HDOJ 2067 小兔的棋盘 DP/卡特兰数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---