AcWing 4211. 序列重排
原题链接
困难
作者:
大笔筒
,
2022-01-15 22:13:01
,
所有人可见
,
阅读 235
#include<iostream>
using namespace std;
const int N=2100;
long long a[N];
long long b[N];//全排列数组
int n;
bool st[N];
void output()
{
for(int i=1;i<=n;i++) cout<<b[i]<<" ";
cout<<endl;
}
void dfs(int ith)
{
if(ith==n+1)
{
output();
return;
}
for(int i=1;i<=n;i++)
{
if(ith==1)//不要忘记回溯!!!
{
b[ith]=a[i];
st[i]=true;
dfs(ith+1);
st[i]=false;
b[ith]=0;
}
else
{
if(st[i]==false &&(a[i]==b[ith-1]*2 || a[i]*3==b[ith-1]) && b[ith-1]!=0)
{
b[ith]=a[i];
st[i]=true;
dfs(ith+1);
st[i]=false;
b[ith]=0;
}
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
dfs(1);
return 0;
}
貌似这一题dfs不是正解,有更好的方法