没有清空向量导致debug了好久
这题难以下手 不知道怎么dfs
原来是用排序函数。
letter[n]=i;
id[i]=n++;
用来储存与设置标记十分巧妙
for(;;) { while(s[p]!=‘:‘&&p<n1)p++; if(p==n1)break; while(s[e]!=‘;‘&&e<n1)e++; for(int i=p+1;i<e;i++) { dad.push_back(id[ s[p-1] ]); son.push_back(id[ s[i] ]); } p++;e++; }
输入方式是一个难点 lrj采用一个父节点对应一个子结点 方便后续的判断，p和e的使用要注意！
然后 设置pai数组用来排序 数组里先是第一个字典序0，1，2，3。。。n-1（对应的是之前被标记的字母，因为字母是从A按顺序排序的 所以这就是第一个字典序） 然后用 next_permutation函数来自动改变其字典序
同时 设置一个posi函数来储存各个位置 相当于位置下标 差即为距离
这两个数组的设置很值得学习
memcpy 快速保存答案。想起在之前有一道求旅行路径的深搜题可以用
这题很有价值 多打几遍
#include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; vector<int>dad,son; int main() { char s[1000]; int letter[10]; int id[256]; while(scanf("%s",s)==1&&s[0]!=‘#‘) { int n=0; for(char i=‘A‘;i<=‘Z‘;i++) { if(strchr(s ,i)!=NULL) { letter[n]=i; id[i]=n++; } } int p=0; int e=0; int n1=strlen(s); dad.clear();son.clear(); for(;;) { while(s[p]!=‘:‘&&p<n1)p++; if(p==n1)break; while(s[e]!=‘;‘&&e<n1)e++; for(int i=p+1;i<e;i++) { dad.push_back(id[ s[p-1] ]); son.push_back(id[ s[i] ]); } p++;e++; } int pai[10]; int posi[10]; int bestposi[10]; for(int i=0;i<n;i++)pai[i]=i; int ans=n; do { for(int i=0;i<n;i++)posi[ pai[i] ]=i; int d=0; for(int i=0;i<dad.size();i++) d=max(d,abs( posi[dad[i]]-posi[ son[i] ] ) ); if(d<ans) { ans=d; memcpy(bestposi,pai,sizeof(pai)); } } while(next_permutation(pai,pai+n)); for(int i=0;i<n;i++)printf("%c ",letter[bestposi[i]]); printf("-> %d\n",ans); } return 0; }
原文：https://www.cnblogs.com/bxd123/p/10352012.html
