洛谷 P1019 [NOIP2000 提高组] 单词接龙(dfs)

题目链接:

https://www.luogu.com.cn/problem/P1019

思路:

1.首先我们对所有字符串做一个预处理得到inc[i][j]这个数组,这个数组的含义是:在字符串 i i i后接上字符串 j j j可以使得字符串增加多少长度;
做这个预处理的理由是,在真正接龙时,想要得到最长的“龙”,必定是一个字符串接在刚刚接上的字符串之后;
2.然后进行暴力搜索即可,注意维护一个数组存储字符串用过的次数,大于等于两次的字符串不能再用;

代码:

#include <bits/stdc++.h>

using namespace std;

const int maxn = 22;
int n;
int used[maxn]; 
int inc[maxn][maxn];  //inc[i][j]:第i个单词后面接第j个单词能增加的长度 

inline int test(string & a, string & b) {
	int len = min(a.length(), b.length());
	for(int i = 1; i < len; ++i) {
		if(a.substr(a.length() - i) == b.substr(0, i)) {
			return b.length() - i;
		}
	}
	return 0;
}

int bst = 0;
void dfs(int id, int len) {
	used[id]++;
	for(int i = 0; i < n; i++) {
		if(inc[id][i] && used[i] < 2) dfs(i, len + inc[id][i]);
	}
	bst = max(bst, len);
	used[id]--;
}

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	cin >> n;
	string s[n];
	for(int i = 0; i < n; ++i) cin >> s[i];
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			inc[i][j] = test(s[i], s[j]);
		}
	}
	char c;
	cin >> c;
	for(int i = 0; i < n; i++) {
		if(s[i][0] == c) dfs(i, s[i].length());	
	}
	cout << bst;
	return 0;	
}
上一篇:学 Win32 汇编[5]: 数据类型与声明


下一篇:学 Win32 汇编[2]: 最简单的 Win32 程序