题目大意:
单词接龙,找出最长的长度的单词。
题解:
由于数据量较小,单词可多次使用,使用后可回溯,考虑dfs。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int n, used[N], ans;
string a[N], start;
void dfs(string word){
int ls = word.length();
ans = max(ans, ls);
for(int i = 1; i <= n; i ++){
int rs = a[i].length();
if(used[i] < 2){
for(int j = 1; j < ls && j < rs; j ++){
if(used[i] < 2 && word.substr(ls - j) == a[i].substr(0, j)){
used[i] ++;
dfs(word + a[i].substr(j));
used[i] --;
}
}
}
}
}
void solve(){
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
cin >> start;
start = "*" + start;
dfs(start);
cout << ans - 1;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int _ = 1; //cin >> _;
while(_--) solve();
return 0;
}
标签:NOIP2000,int,dfs,单词,start,接龙,ans From: https://www.cnblogs.com/Amire/p/18397361