解题报告 P1019 单词接龙【NOIP2000TGT3】

题目内容

P1019

大意：给出 n 个单词，每个单词最多出现两遍，求最长的龙的长度，前单词和后单词之间不能包含。

解题思路

这题一看就很难调细节，直到我看了题解才发现了新世界。

大体的思路非常好想，就是无脑 dfs 下去，但是整道题的难点就在于字符串的拼接处理。

每次 dfs 的时候函数长这样：dfs(string now,int l)，其中 now 是上一个单词，l 是龙的长度，所以根本没必要存龙（我是sb），直接存上一个单词，然后接着拼接就可以了。

然后拼接有一个原则（贪心）：为了保证最后接出来的龙最长，相交的字符串部分需要尽可能的短，所以定义了一个 link() 函数返回的是两个单词之间最小重叠部分的长度。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int n;
string word[22];
int vis[21];
int ans=0;

int link(string a,string b)//返回两个字符串的最小重叠部分的长度
{
    for(int i=1;i<min(a.size(),b.size());i++)//枚举重叠部分的长度
    {
        bool flag=1;
        for(int j=0;j<i;j++)
            if(a[a.size() - i + j] != b[j])//每一位来判
                flag = 0;
        if(flag)
            return i;
    }
    return 0;
}

void dfs(string now,int l)//now为上一个单词，l为龙的长度
{
    ans=max(ans,l);//每次更新一下答案
    for(int i=0;i<n;i++)//枚举下一个单词
    {
        if(vis[i]>=2)//如果已经用过两次了
            continue;
        int c=link(now,word[i]);//获取两个单词间的重叠长度
        if(c)
        {
            vis[i]++;
            dfs(word[i],l+word[i].size()-c);//继续搜
            vis[i]--;
        }
    }
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<=n;i++)
        cin>>word[i];
    dfs(" "+word[n],1);//这里的空格防link函数错误返回
    cout<<ans<<endl;
    return 0;
}