标题：出栈次序 X星球特别讲究秩序，所有道路都是单行线。一个甲壳虫车队，共16辆车，按照编号先后发车，夹在其它车流中，缓缓前行。 路边有个死胡同，只能容一辆车通过，是临时的检查站，如图【p1.png】所示。 X星球太死板，要求每辆路过的车必须进入检查站，也可能不检查就放行，也可能仔细检查。 如果车辆进入检查站和离开的次序可以任意交错。那么，该车队再次上路后，可能的次序有多少种？ 为了方便起见，假设检查站可容纳任意数量的汽车。 显然，如果车队只有1辆车，可能次序1种；2辆车可能次序2种；3辆车可能次序5种。 现在足足有16辆车啊，亲！需要你计算出可能次序的数目。 这是一个整数，请通过浏览器提交答案，不要填写任何多余的内容（比如说明性文字）。
dfs(x,y)
x表示栈中元素个数，y表示出栈元素的个数或者进栈元素的个数
1.
#include<iostream>#include<stack>using namespace std;int count=0,ans=0;stack<int> S;void dfs(int n,int count){if(count>15){ans++;return;}if(!S.empty()){ S.pop(); dfs(n+1,count); S.push(n); S.push(n); dfs(n+1,count+1); S.pop();}if(S.empty()){S.push(n);dfs(n+1,count+1);S.pop();}}int main(){dfs(0,0);cout<<ans;
}
2.
[cpp] view plain copy #include <iostream> #include <algorithm> #include <stdio.h> using namespace std; int MAX=16; int sum=0; void dfs(int x,int y){ if(y==MAX){ sum++; return ; } if(x-1>=0) dfs(x-1,y+1); if(x+1+y<=MAX) dfs(x+1,y); //进栈 } int main( ) { // freopen("d:\\in.txt","r",stdin); dfs(0,0); cout<<sum<<endl; return 0; }