卡特兰数
2026-06-27 17:14:06
发布于:上海
先看一个问题:

注:车站每次可以进多辆火车
问:有多少种可能?
样例组输入#1
3
样例组输出#1
5
你以为可以暴力?
不
我们这么看:
把一个正方形分成两半
一半是合法的,只要超出就是非法的
合法演示:

我们在画一个不合法的:

发现:

得,答案:
#include<bits/stdc++.h>
using namespace std;
int n;
long long f[20];
int main(){
cin>>n;
f[0]=f[1]=1;
for(int i=2;i<=n;i++)f[i]=f[i-1]*(4*i-2)/(i+1);
cout<<f[n];
return 0;
}
全部评论 3
- 置顶
求赞!
2026-06-27 来自 上海
0 再详细一些应该是篇精华帖
2026-06-27 来自 江西
1谢谢
2026-06-27 来自 上海
0
不错
2026-06-27 来自 江西
0





















有帮助,赞一个