ACM 训练日志记录 · 思考 · 成长
提交 / 修改记录
廖夏 / 题目列表训练档案
导出

P1019　[NOIP 2000 提高组] 单词接龙（疑似错题）

来源：洛谷 ★ 1300

字符串DP搜索递推状压DP本次有失误仍在学习已结束复习安排
本题活力0.20按难度、完成结果与训练证据估算

算法如山行则将至

查看原题廖夏 的主页

题目描述

[NOIP 2000 提高组] 单词接龙（疑似错题）

背景

注意：本题为上古 NOIP 原题，不保证存在靠谱的做法能通过该数据范围下的所有数据。本题的难度仅代表设计算法可以通过本题原始数据的难度。

本题为搜索题，本题不接受 hack 数据。关于此类题目的详细内容

NOIP2000 提高组 T3

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish，如果接成一条龙则变为 beastonish，另外相邻的两部分不能存在包含关系，例如 at 和 atide 间不能相连。

输入格式

输入的第一行为一个单独的整数 $n$ 表示单词数，以下 $n$ 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

输出格式

只需输出以此字母开头的最长的“龙”的长度。

说明/提示

样例解释：连成的“龙”为 atoucheatactactouchoose。

$n \le 20$。

样例 1

输入：

5
at
touch
cheat
choose
tact
a

输出：

23

代码

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int MAXN = 25;
int used[MAXN], ans, n;
string words[MAXN];
int canlink(string now, string wd){
	for (int i = 1; i < min(now.length(), wd.length()); i++){
		bool flag = true;
		for (int j = 0; j < i; j++){
			if (now[now.length()-i+j] != wd[j]){flag = false; break;}
		}
		if (flag) return i;
	}
	return 0;
}
void dfs(string last, int len){
//	cout << last << endl;
	ans = max(ans, len);
	for (int i = 1; i <= n; i++){
		if (used[i] < 2){
			int tmp = canlink(last, words[i]);
			if (tmp){
				used[i]++;
				dfs(words[i], len + words[i].length() - tmp);
				used[i]--;
			}
		}
	}
}
int main(){
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> words[i];
	string tmp;
	cin >> tmp;
	dfs(" " + tmp, tmp.length()); // 手动加一，避免在canlink中被i_initial = 1给跳过
	cout << ans;
	return 0;
}