这题的结果是卡塔兰数的2倍,因为有2种可能,只从对角线下方走和只从对角线上方走。
2*catlan(n)即为结果,其中catlan(n)=
不过如果直接利用此公式编写代码的话,需要注意组合数在计算过程中的溢出。
此题不建议直接用公式来计算,因为我们可以容易地找到递推公式。
假设坐标原点位于左上角,dp[i][j]表示只从对角线上方走时,从坐标(0,0)到(i,j)的路径数,所以有如下结果:
dp[0][0]=1
dp[i][j]=dp[i-1][j]+dp[i][j-1]
源代码如下:
#include <iostream>
#include <iomanip>
#include <cmath>
#define PI 3.1415927
using namespace std;
//this fuction has a bug, sum might overflow during the calculation
long long Catlan(int N) {
long long sum = 1;
for(int i=1;i<N; i++) {
sum=sum*(N+1+i)/i;
}
sum/=N;
return sum;
}
int main()
{
int n;
int id=0;
while(cin >> n) {
if(n==-1) break;
long long dp[36][36]={0};
dp[0][0]=1;
for(int i=0; i<=n; i++) {
for(int j=0; j<=i; j++) {
if(i-1>=0)dp[i][j]+=dp[i-1][j];
if(j-1>=0)dp[i][j]+=dp[i][j-1];
}
}
cout << id+1 << " " << n << " " << 2*dp[n][n] << endl;
id++;
}
return 0;
}
分享到:
相关推荐
HDOJ练习题目源码,约100多道题目,附带题目类型等等
杭电acm在线测试的分类,不是很全,分享给大家
有需要2019年杭电多校数据和标程的可以下载参考的,还有官方题解
hduoj专用解题报告,适合初学者入门,可用!@!!
大家在刷题时,总是想找各种类型,或对单一题型的题目,来提高自己,所以就把以前留下来的POJ,HDUOJ题目分类串传上来了
C++ 杭电的几道ACM水题 不值得一提 拿来赚点分
HDUOJ离线版(目前最新的版本),ACMER 的好帮手来啦啊!呵呵。。。版本也是目前最新的哦!
杭电ACM第1001题的代码。这个A+B PROBLEM的变形。初学者只要习惯了就好
主要在hduoj找到的试题,整理成一个文档以便打印,其中2016年的没有A,B,这两个是我最近刚做过,水题懒得往上加了。
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
leetcode 和 oj ACM Practice for algorithm and coding. The exam questions come from POJ, HDU OJ and Leetcode. 母函数 数学 排序
蟠桃记 1 折线分割平面 2 不容易系列之一 2 骨牌铺方格 3 不容易系列之(3)—— LELE的RPG难题 3 Children’s Queue 3 献给杭电五十周年校庆的礼物 3 钥匙计数之二 3 钥匙计数之一 3 母牛的故事 3 ...
为了方便广大没有网络的朋友.......
【2020年6月1日开始做题,在这之前leetcode上的题目做了11道,大学的时候在hduOJ上刷过100多道。刚开始就是打算每天做做官方和群主的题目,现在给自己定了一个月100题的目标,平均每天3-4道,到6月30为止,做了112道...
BZOJ,POJ,LeetCode,USACO,HDUOJ,LA的比赛解决方案 有话要说 嗨,我是Ex10si0n。 该存储库用于记录我的OJ AC代码。 关于我 OIer,Develpoer。 希望这个仓库可以帮助那些通过Probelm ID找到LeetCode或其他OJ解决...
HDUOJ代码备份爬虫,采用Selenium测试框架爬取HDUOJ已通过题目信息并下载到本地打包
前面那个是比较简单的HDUOJ上的题目,浙大的就有点难度,所以这里就收集得比较多了,解答全部都是用C++编码来写的,有需要的去下载,前面还有一个是杭电的
杭电HDUOJ爬虫脚本,采用Selenium测试框架编写,爬取完后会自动调用百度api翻译
这是HDUOJ上面的140道题目的答案,其中大部分都是简单题,有些太简单的就没有收集进去,代码为C/C++,全都AC了的,其中有些有具体的说明是怎么做的,例如博弈论那些
codefores/problemset/还有HDUOJ、POJ和洛谷/这几个文件夹的以后可能还会更新吧,因为无聊的时候可能会去刷刷题,当然其它的也有可能更新,以后的事也说不准。 update 20210123 开始转战。以后有时间偶尔可能会在...