【bzoj3297】[USACO2011 Open]forgot

2014年10月1日1,3231

Description

发生了这么多,贝茜已经忘记了她cowtube密码。然而,她记得一些有用的信息。
首先,她记得她的密码(记为变量P)长度为L(1 <= L<=1,000)字符串,并可以被分成
一个或多个词(不一定是唯一的),词来自于字典中NW(1<=NW<=1,000)个独特的词。
一个词W_i,被定义为一个长度1..20的小写字母序列(‘a’..’z’)。
她还记得她密码中某些字母的位置。
请看下面的例子。贝西知道她的密码看起来像”a??l?ban???????”(’?’代表一个字母,她不记得),
她的字典里有下面的词:
apple
cow
farmer
banana
bananas
pies
贝西有两个可能的密码是的“applebananapies”和“applebananascow”。
给你字典,贝西记得的字母,请找到她的密码。如果有一个以上的密码是可能的,找到字典序最前的。

Input

*第1行:两个空格分隔的整数:L和NW
*第2行:一个字符串,长度为L:P
*第3..N+2W行:第I+2行包含在字典中的第i个字:W_i

Output

*第1行:密码

Sample Input

15 6
a??l?ban???????
apple
cow
farmer
banana
bananas
pies

Sample Output

applebananapies

题解

直接dp。。。

 

 

  • gzz2017年4月6日 下午10:29 回复

    这不是n^3的吗。。

    #1