P1019 [NOIP2000 提高组] 单词接龙
注意：1.相邻不包含2.每个单词最多使用两次3.如果两部分可以接龙，直接退出，因为如果再继续，长度一定变短（因为相邻的会抵销）4.加个特殊字符，这样就可以不用特判了
因为n很小，直接暴力枚举
1.如果两个可以接龙直接合并（注意相邻相同要抵消）
2.暴力枚举每个单词
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
string word[25], t;
int ans = 0,use[25];
int n;
void dfs(string s) {
int ls = s.size();
ans = max(ans, ls);
for (int i = 1; i <= n; i++) {//暴力枚举每个单词
for (int j = 1; j < word[i].size() && j < ls; j++) {//判断不包含
if (use[i] < 2 && s.substr(ls - j, j) == word[i].substr(0, j)) {//判断只能使用两次
use[i]++;
dfs(s + word[i].substr(j));//接龙后的新单词
use[i]--;
break;//已经是最长的了，再继续会变短
}
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> word[i];
cin >> t;
t = '*' + t;//不用特判了
dfs(t);
cout << ans-1;//因为有个*
return 0;
}