您的当前位置:首页正文

标准二维表问题(排列树)

来源:个人技术集锦
#include<bits/stdc++.h>
using namespace std;

int n;
int a[10000];
bool visit[10000];
string ss[10000];
int k=0;
int res=0;

void dfs(int lens,string s){
	if(lens==n){
		for(int i=0;i<k;i++){
			if(s==ss[i])return;
		}
		ss[k++]=s;
		return;
	}
	for(int i=0;i<n;i++){
		if(visit[i]==false){
			visit[i]=true;
			dfs(lens+1,s+to_string(a[i])+" ");
			visit[i]=false;
		}
	}
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		visit[i]=false;
	}
	dfs(0,""); 
	int temp[10000];
	int q=0;
	for(int i=0;i<k;i++){
		string s="";
		for(int j=0;j<ss[i].length();j++){
			if(ss[i][j]!=' '){
				s+=ss[i][j];
			}else{
				temp[q]=stoi(s);
				q++;
				s="";
			}
						
		}
		bool flag=true;
		for(int u=0;u<q/2;u++){
			if(u+1<q/2){
				if(temp[u]>temp[u+1])flag=false;
			}
			if(u+q/2<q){
				if(temp[u]>temp[u+q/2])flag=false;
			} 
		}
		for(int u=q/2;u<q;u++){
			if(u+1<q){
				if(temp[u]>temp[u+1])flag=false;
			}
		}
		if(flag==true){
			/*for(int i=0;i<q/2;i++)cout<<temp[i]<<" ";
			cout<<endl;
			for(int i=q/2;i<q;i++)cout<<temp[i]<<" ";
			cout<<endl;*/
			res++;
		}
		q=0;	
	}
	cout<<res;
	return 0;
}

因篇幅问题不能全部显示,请点此查看更多更全内容