传送门= ̄ω ̄=

思路:建立有向图!对于输入的字符串s[i]和s[j],dis[i][j]表示字符串s[j]接在s[i]后面时的重叠部分的长度。用函数con(i,j)计算dis[i][j]的值(注意!dis[i][j]不一定等于dis[j][i]!)。在函数con中,我采用了STL的双端队列(deque),它可以从容器首位插入元素,并且支持==比较运算。然后再用dfs找最长路,把字符串s[i]和s[j]接起来产生的长度为s[i]的长度+s[j]的长度-dis[i][j]。

特别注意!一开始我就被这个坑了!每个单词可以用2次!

代码:

#include <bits/stdc++.h>
using namespace std;
int n,ans,dis[25][25],book[25];
string s[25];
char c;
void con(int u,int v)
{
    int lim=min(s[u].length(),s[v].length());
    deque<char> scp[2];
    for(int i=1;i<lim;i++)
    {
        scp[0].push_front(s[u][s[u].length()-i]),scp[1].push_back(s[v][i-1]);
        if(scp[0]==scp[1]){dis[u][v]=i;break;}
    }
}
void dfs(int u,int d)
{
    ans=max(ans,d),book[u]++;
    for(int i=1;i<=n;i++)if(book[i]<2&&dis[u][i])dfs(i,d+s[i].length()-dis[u][i]);
    book[u]--;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)con(i,j);
    cin>>c;
    for(int i=1;i<=n;i++)
        if(s[i][0]==c)
            dfs(i,s[i].length());
    cout<<ans;
    return 0;
}

至于vjudge上的HRBUST – 1213,有多组数据。。。
所以一开始我蜜汁WA。。。
代码:

#include <bits/stdc++.h>
using namespace std;
int n,ans,dis[25][25],book[25];
string s[25];
char c;
void con(int u,int v)
{
    int lim=min(s[u].length(),s[v].length());
    deque<char> scp[2];
    for(int i=1;i<lim;i++)
    {
        scp[0].push_front(s[u][s[u].length()-i]),scp[1].push_back(s[v][i-1]);
        if(scp[0]==scp[1]){dis[u][v]=i;break;}
    }
}
void dfs(int u,int d)
{
    ans=max(ans,d),book[u]++;
    for(int i=1;i<=n;i++)
        if(book[i]<2&&dis[u][i])dfs(i,d+s[i].length()-dis[u][i]);
    book[u]--;
}
int main()
{
    while(ans=0,memset(dis,0,sizeof(dis)),memset(book,0,sizeof(book)),cin>>n)
    {
        for(int i=1;i<=n;i++)cin>>s[i];
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)con(i,j);
        cin>>c;
        for(int i=1;i<=n;i++)if(s[i][0]==c)dfs(i,s[i].length());
        cout<<ans<<endl;
    }
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *