
没有清空向量导致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+;i<e;i++)
{
dad.push_back(id[ s[p-] ]);
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[];
int letter[];
int id[];
while(scanf("%s",s)==&&s[]!='#')
{ int n=;
for(char i='A';i<='Z';i++)
{
if(strchr(s ,i)!=NULL)
{
letter[n]=i;
id[i]=n++;
}
}
int p=;
int e=;
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+;i<e;i++)
{
dad.push_back(id[ s[p-] ]);
son.push_back(id[ s[i] ]);
}
p++;e++;
}
int pai[];
int posi[];
int bestposi[];
for(int i=;i<n;i++)pai[i]=i;
int ans=n;
do
{ for(int i=;i<n;i++)posi[ pai[i] ]=i;
int d=;
for(int i=;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=;i<n;i++)printf("%c ",letter[bestposi[i]]);
printf("-> %d\n",ans);
}
return ;
}