专栏文章

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

yygg_pls
P1044题解参与者 2已保存评论 4

文章操作

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

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

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

题意简述

给定数字序列 1,2,…,n1, 2, \ldots, n，通过栈的 push 和 pop 操作，求可能得到的所有输出序列的总数。

题目分析

本题属于组合数学问题，关键在于理解栈操作序列与卡塔兰数（Catalan numbers）之间的关系。对于一个长度为 nn 的输入序列，其合法的栈操作序列数量即为第 nn 个卡塔兰数。

卡塔兰数性质

卡塔兰数 CnC_n 满足以下递推关系：
Cn=∑i=0n−1Ci×Cn−1−i其中C0=1C_n = \sum_{i=0}^{n-1} C_i \times C_{n-1-i} \quad \text{其中} \quad C_0 = 1
闭合形式为：
Cn=1n+1(2nn)=(2n)!n!(n+1)!C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{n!(n+1)!}

算法选择

由于 n≤18n \leq 18，可以采用动态规划的方法计算卡塔兰数，时间复杂度为 O(n2)O(n^2)。

代码实现

CPP
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int dp[20]={0};
	dp[0]=1;
	for(int i=1;i<=n;i++){
    	for(int j=0;j<i;j++){
			dp[i]+=dp[j]*dp[i-j-1];
		}
	}
	cout<<dp[n];
	return 0;
}

复杂度分析

  • 时间复杂度：O(n2)O(n^2)
  • 空间复杂度：O(n)O(n)

评论

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

正在加载评论...