题目抽象：给出一个字母的邻接关系字符串。字母的带宽为一个字母排列序列中，该字母与其邻接的字母在序列中的小标差值的绝对值的最大值。一个字母排列的带宽为最大的字母带宽。求一个带宽最小的字母排列序列。并求出带宽。
思路：由于字母最多只有8个。所以可以暴力枚举各种排列，求出每种排列的带宽。
扩展：如果数据量更大的情况下。进行优化的话，并不需要枚举各种排列。 记录当前得到的最优值v。如果发现某个字母的带宽大于等于当前的最优值，那么这个排列必定不是最优的。
如果发展到某字母，该字母还有m个字母没有排列。那么该字母最小的带宽为m。如果m都大于等于v了,那么该排列可以舍弃。
注意数据结构的使用，万丈高楼平地起。数据结构才是关键。 下面的代码值得我学习。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <vector> 7 using namespace std; 8 9 const int MS=256; 10 11 int id[MS],letter[MS]; 12 13 int main() 14 { 15 char str[MS]; 16 while(scanf("%s",str)==1&&str[0]!=‘#‘) 17 { 18 int n=0; 19 for(char ch=‘A‘;ch<=‘Z‘;ch++) 20 if(strchr(str,ch)!=NULL) 21 { 22 id[ch]=n++; 23 letter[id[ch]]=ch; 24 } 25 int len=strlen(str); 26 int s=0,t=0; 27 vector<int> u,v; 28 while(1) 29 { 30 while(s<len&&str[s]!=‘:‘) 31 s++; 32 if(s==len) 33 break; 34 while(t<len&&str[t]!=‘;‘) 35 t++; 36 for(int i=s+1;i<t;i++) 37 { 38 u.push_back(id[str[s-1]]); 39 v.push_back(id[str[i]]); 40 } 41 s++; 42 t++; 43 } 44 int P[MS],bestP[MS],pos[MS],ans=n; 45 for(int i=0;i<n;i++) 46 P[i]=i; 47 do 48 { 49 for(int i=0;i<n;i++) 50 pos[P[i]]=i; 51 int bandWidth=0; 52 for(int i=0;i<u.size();i++) 53 { 54 bandWidth=max(bandWidth,abs(pos[u[i]]-pos[v[i]])); 55 } 56 if(bandWidth<ans) 57 { 58 ans=bandWidth; 59 memcpy(bestP,P,sizeof(P)); 60 } 61 }while(next_permutation(P,P+n)); 62 63 for(int i=0;i<n;i++) 64 printf("%c ",letter[bestP[i]]); 65 printf("-> %d\n",ans); 66 } 67 return 0; 68 }
原文：http://www.cnblogs.com/hutaishi/p/4538655.html