【NOIP2000】【Luogu1019】单词接龙

提交：
https://www.luogu.org/problemnew/show/P1019
http://codevs.cn/problem/1018/
https://vijos.org/p/1311

直接搜索就好啦，几乎没什么技巧，就是状态建模会有点难想到(应该有多种)
包含的情况可以证明是不需要考虑的,因为包含后一定不会比不包含要来的长

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int maxn = 30;
int n, ans, used[maxn];
string w[maxn];
//找到a的末尾与b的前端重复的子串并返回其长度
int find(string a, string b){
    int mm = min(a.size(), b.size());
    for(int i = 1; i <= mm; i++)
        if(a.substr(a.size()-i)==b.substr(0,i))
            return i;
    return 0;
}
//深度优先搜索寻找解, 状态：s为当前字符串
void dfs(string s){
    ans = max(ans, (int)s.size());
    for(int i = 1; i <= n; i++)if(used[i]<2){
        int t = find(s, w[i]);
        if(t == s.size() && s!=w[0])continue;//包含关系
        if(t){
            used[i]++;
            dfs(s.substr(0,s.size()-t)+w[i]);
            used[i]--;
        }
    }
}
int main(){
    cin>>n;
    for(int i = 1; i <= n; i++)cin>>w[i];
    cin>>w[0];
    dfs(w[0]);
    cout<<ans<<"\n";
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/79684486