首页 > 代码库 > SDUT 1266-出栈序列的统计（DFS）
SDUT 1266-出栈序列的统计（DFS）
出栈序列的统计
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，……，n，经过一系列操作可能得到的输出序列总数。
输入
一个整数n（1<=n<=15)。
输出
一个整数，即可能输出序列的总数目。
示例输入
3
示例输出
5
一系列操作后结束的条件为：
所有的元素都已执行过入栈操作。
由此爆搜。。据说dp可解。以后回头再看
#include <iostream> #include <cstdio> #include <algorithm> #include <set> #include <cctype> #include <cstring> #include <cmath> #include <vector> using namespace std; const int INF=0x3f3f3f3f; int n,ans; void dfs(int num,int top) { if(num==n) { ans++; return ; } dfs(num+1,top+1); if(top>0) dfs(num,top-1); } int main() { while(scanf("%d",&n)!=EOF) { ans=0; dfs(0,0); printf("%d\n",ans); } return 0; }
SDUT 1266-出栈序列的统计（DFS）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。