如果直接看这道题,很容易陷入一个思维误区,即直接使用DFS+栈进行解题
观察样例,很容易给我们一个“这是全排列”的错觉,但实际上他有一个限制,因此可能反而不去考虑全排列了
但事实上,此题输出为一个“缩小”后的全排列。考虑“缩小”的规则,并结合“栈”的性质,我们意识到这是“后进先出”所导致的
拓展“后进先出”这一结论,可以推广出一个规律:对于任何一个输出序列,其中的任意一数【其后面比它更小的数】,这个整体必为倒序,如“1423”即为不合法序列
于是,此题就转化为了求全排列+判断合法性
从这道题中,我们意识到了观察“结论”的特性,并以之倒推解题思路的重要性.在其中,也有着“复杂问题转化为多个简单问题和”的深刻思想。
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=50;
int n;
bool vis[MAXN];
int stck[MAXN],top=0;
int tmp[MAXN],tmpTop=0;//
void getLowToTmp(int index,int nowValue){//将编号之后比nowValue小的数字放入tmp数组
for(int i=index+1;i<=top;i++){
if(stck[i]<nowValue){
tmp[++tmpTop]=stck[i];
}
}
}
/**
index:nowValue的编号(栈中的)
*/
bool judge_low(int nowValue,int index){//是否 比nowValue小的数字都倒序
getLowToTmp(index,nowValue);
int minn=nowValue;
bool isOk=true;//是否都倒序
for(int i=1;i<=tmpTop;i++){//如果从index+1开始向后枚举,枚举到的数都比当前的min小,则更新(此时合法),否则说明非倒序
if(tmp[i]>minn){
isOk=false;
break;
}
minn=min(minn,tmp[i]);
}
tmpTop=0;
return isOk;
}
bool judge(){//是否合法
for(int i=1;i<=top;i++){
int nowValue=stck[i];
if(judge_low(nowValue,i)){//是否 比nowValue小的数字都倒序
continue;
}else{
return 0;
}
}
return 1;
}
int cnt=0;//输出计数 (超过20则关闭程序)
void dfs(int nowNum,int siz){
if(cnt==20){
return;
}
if(siz==n){
if(judge()){
for(int i=1;i<=top;i++)cout<<stck[i];
cout<<endl;
cnt++;
}
return;
}
vis[nowNum]=1;
for(int i=1;i<=n;i++){
if(i!=nowNum&&(!vis[i])){
stck[++top]=i;
dfs(i,siz+1);
top--;
}
}
vis[nowNum]=0;
}
int main(){
scanf("%d",&n);
dfs(0,0);
return 0;
}