題目描述

這里有n列火車將要進站再出站……
但是，每列火車只有1節(jié)---那就是車頭……
描述
有n列火車按1到n的順序從東方左轉進站，這個車站是南北方向的，它雖然無限長，只可惜是一個死胡同，而且站臺只有一條股道，火車只能倒著從西方出去，而且每列火車必須進站，先進后出。
（某生：不就是個棧嗎？每次可以讓右側頭火車進棧，或者讓棧頂火車出站？
老師：閉嘴！）
就像這樣：
? 出站<——-? ? <——進站
? ? ? ? ? ? ? ? ? ? |車|
? ? ? ? ? ? ? ? ? ? |站|
? ? ? ? ? ? ? ? ? ? |__|
現在請你按《字典序》輸出前20種可能的出棧方案。

?

輸入

一個整數 n<=20

?

輸出

按照《字典序》輸出前20種答案，每行一種，不要空格

?

樣例輸入

復制樣例數據

3

樣例輸出

123 132 213 231 321

#include <bits/stdc++.h> using namespace std;int n; int ans[25]; int vis[25]; int t=0;int pd() {int maxx;for(int i=0;i<n;i++){int flag=0;for(int j=i+1;j<n;j++){if(ans[j]<ans[i]){if(flag==0){maxx = ans[j];flag = 1;}if(maxx<ans[j])return 0;}}}return 1; }void dfs(int cur) {if(cur==n&&t<=20)//達到出棧20并且輸出小于20個 {if(pd()) //如果該序列符合這種入棧出棧的序列 輸出 {for(int i=0;i<n;i++){printf("%d",ans[i]);}printf("\n");t++;return;}}for(int i=1;i<=n;i++) //制造全排列的數 不需要一直造 當找到了20個之后 直接return {if(!vis[i]){ans[cur] = i;vis[i] = 1;dfs(cur+1);if(t==20)return;vis[i] = 0;}} } int main() {scanf("%d",&n);dfs(0); }

?

參考：https://blog.csdn.net/Go_Accepted/article/details/61199971?utm_source=blogxgwz2

模擬進棧出棧的問題，這里因為是有序的，所以每個數字后面比這個數字小的幾個數字應該是逆序

例如 14532 符合進棧出棧序列 ?對于4之后比4小的有2、3必須是逆序32排列

?

判斷代碼：

int pd()

{

????int maxx;

????for(int i=0;i<n;i++) //遍歷每一個數之后有沒有比自身小的

????{

????????int flag=0;

????????for(int j=i+1;j<n;j++)

????????{

????????????if(ans[j]<ans[i])

?//有小于自身的數的話 要保證之后比自身數小的數都要比ans[j]小 保證逆序

????????????{

????????????????if(flag==0)

????????????????{

????????????????????maxx = ans[j];

????????????????????flag = 1;

????????????????}

????????????????if(maxx<ans[j])

????????????????????return 0;

????????????}

????????}

????}

????return 1;

}

轉載于:https://www.cnblogs.com/hao-tian/p/10152172.html

總結

以上是生活随笔為你收集整理的火车进栈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。