ZJU/ZOJ 2349 Mix and Build 解题报告

题目大意是给出一个字典，要求在其中找出一条最长单词链，链中的单词要求满足前后两个单词字数只相差1，且只有1个字母不同。

见到这种题目很直观地会想到Trie树的模型，不过我没想到怎样将字符串之间的关系转化为Trie树中的关系，所以还是对字符串进行预处理后用了朴素的DP。具体方法是先对每个字符串按字母顺序排序，然后对所有字符串按长度大小排序，接着对长度相差1的字符串进行匹配DP即可。有一个优化是如果当前的连续区域的长度不必已知最长链长度大则这部分不需要进行匹配操作。不过记得要注意一个字符串可以匹配多个字符串，我一开始误将题目中没有重复的单词引申理解成了每个字符串只能匹配一个字符串……

3008524 2008-07-27 11:37:51 Accepted 2349 FPC 00:01.73 868K IwfWcf@LZOI