csu 1772 漫漫上学路（卡特兰数）

最新推荐文章于 2021-07-04 00:59:34 发布

acm_cxq

最新推荐文章于 2021-07-04 00:59:34 发布

阅读量635

点赞数

分类专栏：卡特兰数文章标签： ACM

本文链接：https://blog.csdn.net/acm_cxq/article/details/52270447

版权

卡特兰数专栏收录该内容

2 篇文章

订阅专栏

本篇介绍了一道经典的卡特兰数算法题目，背景设定在一个被水淹没一半的大学校园中，主人公需要从宿舍出发，在限定时间内找到到达机房的所有最短路径数目。文章提供了完整的解题思路与C++实现代码。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

漫漫上学路

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 104 Solved: 54
[ Submit][ Status][ Web Board]

Description

对于csuxushu来说，能够在CSU（California State University）上学是他一生的荣幸。CSU校园内的道路设计的十分精巧，由n+1条水平道路和n+1条竖直道路等距交错而成，充分体现了校园深厚的文化底蕴。然而不幸的是CS市每到夏季，天降大雨，使得CSU常常形成“CS海”的奇观，今年，也就是2016年同样也不例外，校园有一半的区域被淹了。
由于要进行一年一度激动人心的省赛选拔了，起迟了的csuxushu赶紧从寝室背着一包模板前往机房，好奇的csuxushu发现虽然道路被淹了，但是只有左上三角区域受到影响，也就是说他可以在副对角线以下的道路畅通行走。在这个惊人的场景下，csuxushu做了一个惊人的决定，他要算出他有多少种前往机房的最短路线。然而只有10分钟了，这时候他想到了你——全CSU最厉害的程序员来帮助他解决这个问题。
需要指出的是CSU可以看做左下顶点为csuxushu的寝室（0,0），右上顶点为机房（n,n）的方形区域。

Input

多组数据。每组数据只有一行，为一个整数n（1 ≤n ≤30）。

Output

每组数据输出一行，即由寝室到机房的最短路线方案数。测试数据保证结果为64位整数。

Sample Input

Sample Output

HINT

14条最短路线如下

思路：卡特兰数模板题，注意这里不给取模，那就不能给C数组打表了，n比较小，暴力求把

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define N 35
long long C(long long a,long long b)
{
    long long ans=1;
    for(int i=1;i<=b;i++,a--)
        ans=ans*a/i;
    return ans;
}
int main()
{
    long long n;
    while(~scanf("%lld",&n))
    {
        printf("%lld\n",C(2*n,n)-C(2*n,n-1));
    }
    return 0;
}