点击打开链接
//dfs回溯剪枝 //使用递归枚举法实现搜索时,相当于对一棵解答树进行先序遍历,解答树的节点数近似为n!个,10!近似为3.6*1e6 //剪枝:1.可行性剪枝：该方法判断继续搜索能否得到答案，如果不能则直接回溯 //2.最优性剪枝：又称为上下界剪枝，是一种重要的剪枝策略，它记录当前得到的最优解，如果当前节点已经无法产生比当前最优解更优的解时，可以提前回溯 #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> using namespace std; const int maxn=10+5; int main() { char s[1000]; while(scanf("%s",s)==1) { if(s[0]=='#') break; int len=strlen(s); int p=0,q=0,n=0; int id[256],letter[maxn]; for(char ch='A';ch<='Z';ch++) { if(strchr(s,ch)!=NULL) { id[ch]=n++; letter[id[ch]]=ch; } } s[len]=';'; vector<int>G; G.clear(); vector<int>G1; G1.clear(); for(;;) { while(p<len+1&&s[p]!=':') p++; while(q<len+1&&s[q]!=';') q++; for(int i=p+1;i<q;i++) { G.push_back(id[s[p-1]]); G1.push_back(id[s[i]]); } p++; q++; if(q==len+1) break; } /*for(int i=0;i<G.size();i++) printf("%d %d\n",G[i],G1[i]);*/ int P[maxn],ans=maxn; int best[maxn],bp[maxn]; for(int i=0;i<n;i++) P[i]=i; do{ for(int i=0;i<n;i++) bp[P[i]]=i; int pos=0; for(int i=0;i<G.size();i++) pos=max(pos,abs(bp[G[i]]-bp[G1[i]])); if(ans>pos) { ans=pos; memcpy(best,P,sizeof(P)); } }while(next_permutation(P,P+n)); for(int i=0;i<n;i++) printf("%c ",letter[best[i]]); printf("-> %d\n",ans); } return 0; }