明白了dfs,就明白了这一题
求方案数,以及保留方案
#include<bits/stdc++.h>
using namespace std;
const int N=100,INF=1e9;
int n,pre[N],post[N];
int dfs(int prel,int prer,int postl,int postr,string &ans){
if(prel>prer) return 1;//可遍历完,说明存在一种方案
if(pre[prel]!=post[postr]) return 0;//不存在的方案
int cnt=0;
for(int i=prel;i<=prer;i++){
string l,r;
int l_cnt=dfs(prel+1,i,postl,postl+i-prel-1,l);//len=i-prel-1+1
int r_cnt=dfs(i+1,prer,postl+i-prel,postr-1,r);
cnt+=l_cnt*r_cnt;
if(l_cnt!=0&&r_cnt!=0){
ans=l+to_string(pre[prel])+" "+r;
}
}
return cnt;
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>pre[i];
for(int i=0;i<n;i++) cin>>post[i];
string tmp;
if(dfs(0,n-1,0,n-1,tmp)>=2) cout<<"No";
else cout<<"Yes";
cout<<endl<<tmp.substr(0,tmp.size()-1);
}