题解 P1754 【球迷购票问题】

· · 题解

看题解好像没有具体说明为什么是catalan，所以就简单说明一下

一个A买票后售票处会积累50元钱

一个B买票需要售票处找零50元钱

说明在一个B买票前至少需要一个A买过票

那么我们就可以将A看作左括号，B看作右括号

问题就是要求合法得括号匹配，即Catalan数

n得范围开long long不会溢出 所以用一个快一些的递推公式

h(n)=h(n−1)∗(4∗n−2)/(n+1) 
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;

int n;
ll cat[50];

int main()
{
    scanf("%d",&n);
    cat[0]=cat[1]=1;

    for(int i=2;i<=n;++i)
    cat[i]=cat[i-1]*(4*i-2)/(i+1);

    cout<<cat[n];
    return 0;
}//niiick