题目链接:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=385#problem/L

思路:回溯 或者 stl函数求全排列验证,下面是第二种;

code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 500000
int map[50][50],vis[50];//map确定字母间的关系,vis用于提取原始串中的字母
int mar,k;
char word1[MAX],word2[50],word3[50];//word1存输入串,word2存提取后的字母串,word3存最小值对应的串
int check()//检查当前串对应最大值
{
int ma=0,sum=0;
int i,j;
for(i=0;i<k;i++)//模拟过程
{
sum=0;
for(j=i+1;j<k;j++)
{
sum++;
if(map[word2[i]-‘A’][word2[j]-‘A’]==1)
{
if(sum>ma)
ma=sum;
}
}
}
return ma;
}
int main()
{
int i,n,t=0,flag=0,min;
char a,b;
while(gets(word1),word1[0]!=’#’)
{
k=0;
memset(map,0,sizeof(map));
memset(word3,0,sizeof(word3));
memset(word2,0,sizeof(word2));
memset(vis,0,sizeof(vis));
n=strlen(word1);
min=0x3f3f3f;
for(i=0;i<n;i++)//输入处理
{
if(word1[i+1]==’:’)
{
a=word1[i];
vis[a-‘A’]=1;
while(word1[i]!=’;’&&i<n)
{
b=word1[i++];
if(b>=’A’&&b<=’Z’)
{
vis[b-‘A’]=1;
map[a-‘A’][b-‘A’]=1;
map[b-‘A’][a-‘A’]=1;
}
}
}
}
for(i=0;i<30;i++)
{
if(vis[i])
word2[k++]=i+’A’;
}

sort(word2,word2+k);
do
{
mar=check();
if(mar<min)
{
min=mar;
strcpy(word3,word2);
}
}while(next_permutation(word2,word2+k));
for(i=0;i<k;i++)
printf(“%c “,word3[i]);
printf(“-> %d\n”,min);
}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation