[Luogu2462][SDOI2007]游戏(字符串Hash,最长路)

发布于 2018-05-28  341 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[Luogu2462][SDOI2007]游戏(字符串Hash,最长路)

Description

小木木和小凳子试两个聪明的孩子,他们五岁的时候就开始学习英语了。
英语老师教他们玩一个很简单的游戏。老师给他们一张全小写并无特殊符号的英语单词表,单词表如下:
ab arc arco bar bran carbon carbons
cobra crab crayon narc
然后让他们从单词表里找词语接龙。接龙的规则如下:
1 前一个单词拥有的所有字母,在后一个单词里必须出现,而且字母出现次数不少于前一单词。
2 后一个单词的长度比前一个单词的长度恰好多1
对于以上例子,一合法的接龙为:
ab bar crab cobra carbon carbons
他们之中,谁接龙的长度长,谁就赢了。小木木肯定不想输,所以找到你,放肆撒娇,导致你因为不想再被打扰而帮他了。至于小凳子呢??说不定找郭大牛去了。嘿嘿,你和郭大牛的编程比赛??加油吧!!!

Tag

字符串Hash,最长路

解决思路

标签中给的虚树?
把单词\(Hash\)起来,然后枚举加上哪一个字母,再\(hash\)判断是否存在这样的单词,如果存在则连边,这样可以构建出一张\(DAG\),在\(DAG\)上动态规划求最长路就好。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[Luogu2462][SDOI2007]游戏(字符串Hash,最长路)


HNCJ OIer