专栏文章

题解：P1044 [NOIP 2003 普及组] 栈

DDoraeman
P1044题解参与者 7已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@mipum8u7
此快照首次捕获于
2025/12/03 18:12
3 个月前
此快照最后确认于
2025/12/03 18:12
3 个月前
查看原文

提示

我们可以计算多个不同的 nn，通过观察找规律可得，这道题的答案符合卡特兰数的规律。

卡特兰数

卡特兰数是组合数学中一种常出现于各种计数问题中的数列。
卡特兰数的前几项为（从第 00 项开始）：
1,1,2,5,14,42,132,429,1430,...1,1,2,5,14,42,132,429,1430,...。
卡特兰数的 CnC_n 的递推规律是：
Cn=C0Cn−1+C1Cn−2+...+Cn−2C1+Cn−1C0C_{n}=C_0C_{n-1}+C_1C_{n-2}+...+C_{n-2}C_1+C_{n-1}C_0。
根据上面这个递推公式，直接写代码即可。

代码

递推写法

CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL C[25];

int main(){
    int n; cin >> n;
    
    C[0] = 1;
    for(int i=1; i<=n; i++)
    	for(int j=0; j<i; j++)
    		C[i] += C[j] * C[i-j-1];
    		// 递推公式 
			
	cout << C[n]; 
}

递归写法

CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL C(int x){
	if(x == 0) return 1;
	LL ans = 0;
	for(int i=0; i<x; i++)
		ans += C(i) * C(x-i-1);
		// 递推公式 
	return ans;
}

int main(){
    int n; cin >> n;
    cout << C(n);
}

打表

当然，在我们知道答案的规律之后，也可以在网上搜索卡特兰数的前几项，然后直接打表得到答案。
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL ans[] = {1, 1, 2, 5, 14, 42, 
			132, 429, 1430, 4862, 16796, 
			58786, 208012, 742900, 2674440, 
			9694845, 35357670, 129644790, 477638700};
// 刚好到第 18 项  

int main(){
    int n; cin >> n;
    cout << ans[n];
}

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...