题目背景
栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。
栈有两种最重要的操作,即 pop(从栈顶弹出一个元素)和 push(将一个元素进栈)。
栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时,想到了一个书上没有讲过的问题,而他自己无法给出答案,所以需要你的帮忙。
题目描述
宁宁考虑的是这样一个问题:一个操作数序列,1 , 2 , ⋯ , n 1,2,\cdots ,n 1 , 2 , ⋯ , n (图示为 1 到 3 的情况),栈 A 的深度大于 n n n 。
现在可以进行两种操作:
将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的 push 操作);
将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的 pop 操作)。
使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由 1 2 3 生成序列 2 3 1 的过程。
(原始状态如上图所示)
你的程序将对给定的 n n n ,计算并输出由操作数序列 1 , 2 , ⋯ , n 1,2,\cdots,n 1 , 2 , ⋯ , n 经过操作可能得到的输出序列的总数。
输入格式
输入文件只含一个整数 n n n (1 ≤ n ≤ 18 1 \leq n \leq 18 1 ≤ n ≤ 18 )。
输出格式
输出文件只有一行,即可能输出序列的总数目。
输入输出样例
输入 #1
输出 #1
说明/提示
【题目来源】
NOIP 2003 普及组第三题
思路
暴力搜索
考虑每次操作从栈中弹出还是向栈中增加新的数。
x,string cur,string res)```表示已经考虑完第 $x$ 个数,栈中的序列为 $cur$,弹出的序列为 $res$;递归入口为```DFS(0,"","")```,当 $res$ 的长度为 $n$ 时,存入哈希表,最终的答案为哈希表的大小。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 ```cpp /****************************************************************** Copyright: 11D_Beyonder All Rights Reserved Author: 11D_Beyonder Problem ID: Luogu P1044 Date: 2021 Mar. 16th Description: DFS *******************************************************************/ #include<iostream> #include<string> #include<unordered_set> using namespace std; unordered_set<string>ans; int n; void DFS(int x,string cur,string res){ if(res.size()==n){ ans.insert(res); return; } if(cur.length()){ //栈中弹出一个 string nxt=cur; nxt.pop_back(); DFS(x,nxt,res+cur.back()); } //进栈 if(x==n){ return; } string nxt=cur+(char)(x+'1'); DFS(x+1,nxt,res); } int main() { cin>>n; DFS(0,"",""); cout<<ans.size()<<endl; return 0; }
上面的代码妥妥超时了,第一反应是:string
类型的拷贝太耗时间,且每次得到的 r e s res res 都不同,没必要去重。将哈希表去掉后可以看到,我们只在意 r e s res res 的长度,并不在意 c u r cur c u r 和 r e s res res 的内容,因此直接用int
类型即可。
x,int cur,int res)```表示当前已经考虑完第 $x$ 个数,栈中有 $cur$ 个数,已经输出 $res$ 个数的状态;入口为```DFS(0,0,0)```,当 $res 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 显然是超时了,$n=18$ 时有 $477638700$ 种情况。 ```cpp /****************************************************************** Copyright: 11D_Beyonder All Rights Reserved Author: 11D_Beyonder Problem ID: Luogu P1044 Date: 2021 Mar. 16th Description: DFS *******************************************************************/ #include<iostream> using namespace std; int n; int ans; void DFS(int x, int cur, int res) { if (res == n) { ++ans; return; } if (cur) { //栈中弹出一个 DFS(x, cur - 1, res + 1); } //进栈 if (x == n) { return; } DFS(x + 1, cur + 1, res); } int main() { cin >> n; DFS(0, 0, 0); cout << ans << endl; return 0; }
记忆化搜索
在上述搜索的参数中,显然有 r e s + c u r = x res+cur=x res + c u r = x ,我们记录了多余的状态。采用记忆化搜索的方式,当 c u r + r e s = n cur+res=n c u r + res = n 时,返回临界值 1 1 1 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <iostream> using namespace std;int n;int f[22 ][21 ];int DFS (int cur, int res) { if (f[cur][res]) { return f[cur][res]; } if (cur + res == n) { return f[cur][res] = 1 ; } int ans = 0 ; if (cur) { ans += DFS (cur - 1 , res + 1 ); } ans += DFS (cur + 1 , res); return f[cur][res] = ans; } int main () { cin >> n; cout << DFS (0 , 0 ) << endl; return 0 ; }
卡特兰数
令 f n f_n f n 表示 n n n 个数出栈入栈的方法数,则对于 f n f_n f n ,可以用第一个入栈数字出栈的时机作为标准。若首个入栈数字 x x x 在 n n n 个数字中第 k k k 个出栈,那么产生的方案数为 f k − 1 × f n − k f_{k-1}\times f_{n-k} f k − 1 × f n − k :f k − 1 f_{k-1} f k − 1 为在 x x x 之前出栈之前那 k − 1 k-1 k − 1 个数的方案,f n − k f_{n-k} f n − k 为在 x x x 出栈之后那 n − k n-k n − k 个数的方案。
枚举 k k k ,有 f n = ∑ k = 1 n f k − 1 × f n − k f_n=\sum\limits_{k=1}^n f_{k-1}\times f_{n-k} f n = k = 1 ∑ n f k − 1 × f n − k ,这就是卡特兰数的一个递推式。
用 H n H_n H n 表示卡特兰数的第 n n n 项,有 H n = 4 n − 2 n + 1 H n − 1 H_n=\frac{4n-2}{n+1}H_{n-1} H n = n + 1 4 n − 2 H n − 1 ,且 H 0 = 1 H_0=1 H 0 = 1 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <iostream> using namespace std;typedef long long ll;ll f[19 ]; int main () { f[0 ] = 1 ; for (int i = 1 ;i <= 18 ;i++) { f[i] = f[i - 1 ] * (4 * i - 2 ) / (i + 1 ); } int n; cin >> n; cout << f[n] << endl; return 0 ; }