P1754 球迷购票问题 (卡特兰数,递推)

题目背景

盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。

按售票处规定，每位购票者限购一张门票，且每张票售价为50元。在排成长龙的球迷中有N个人手持面值50元的钱币，另有N个人手持面值100元的钱币。假设售票处在开始售票时没有零钱。试问这2N个球迷有多少种排队方式可使售票处不致出现找不出钱的尴尬局面。

题目描述

例如当n=2是，用A表示手持50元面值的球迷，用B表示手持100元钱的球迷。则最多可以得到以下两组不同的排队方式，使售票员不至于找不出钱。

第一种:A A B B

第二种:A B A B

[编程任务]

对于给定的n (0≤n≤20),计算2N个球迷有多少种排队方式，可以使售票处不至于找不出钱。

输入输出格式

输入格式：

一个整数，代表N的值 

输出格式：

一个整数，表示方案数

输入输出样例

输入样例#1： 

2

输出样例#1： 

   2

 

Solution

这是道我都能秒切的水题.然后关于这个题,有两个解法.

1. 数学

这个就是赤裸裸的卡特兰数.不解释.

只上一个卡特兰数的公式.

2. DP

状态定义:

f [ i ][ j ] 表示前 i 个人里面 有 j 张50 的.

然后决策有两种. 

第一 拿100的      

 f[i][j]+=f[i-1][j-1];

第二 拿50的

 f [ i ] [ j ]+=f [ i - 1 ] [ j + 1 ];

代码

只写了卡特兰.

#include<iostream>
using namespace std;
typedef long long ll;
int n;
ll cat[50];
int main()
{
    cin>>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;
}