题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1583
题目意思:
给你n个子串,合并之后的最小长度
解题思路:
因为这题的规模很小,用DFS枚举就OK
比较麻烦点的就是合并的函数,枚举合并的长度就OK啦
水题,纯粹娱乐。
代码:
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
string data[10];
char tmp[10];
int vis[10];
int ans;
int n;
string merge(string a,string b)
{
int len1=a.length();
int len2=b.length();
int len = min(len1,len2);
string ret=a+b;
for(int i=1;i<=len;i++)
{
bool flag = true;
for(int j=1;j<=i;j++)
{
if(a[len1-i+j-1]!=b[j-1])
{
flag=false;
break;
}
}
if(flag)
{
ret=a;
for(int j=i;j<len2;j++)
ret+=b[j];
}
}
return ret;
}
void dfs(string tmp,int deep)
{
if(deep>=n-1)
{
if(ans>tmp.length())
ans=tmp.length();
return;
}
for(int i=0;i<n;i++)
{
if(!vis[i])
{
string tmp2 = merge(tmp,data[i]);
vis[i]=1;
dfs(tmp2,deep+1);
vis[i]=0;
}
}
}
int main()
{
while(~scanf("%d",&n))
{
for(int i=0;i<n;i++)
{
scanf("%s",tmp);
data[i]=string(tmp);
}
memset(vis,0,sizeof(vis));
ans=0x3f3f3f;
for(int i=0;i<n;i++)
{
vis[i]=1;
dfs(data[i],0);
vis[i]=0;
}
printf("%d\n",ans);
}
return 0;
}