3297: [USACO2011 Open]forgot
3297: [USACO2011 Open]forgot
HansBug
发布于 2018-04-11 10:17:10
发布于 2018-04-11 10:17:10
3297: [USACO2011 Open]forgot
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 69 Solved: 51
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
HINT
Source
题解：看了半天一直还在想着怎么套AC自动机，直到看到了N<=1000这个复杂度，于是感觉暴力DP都能过啦么么哒
1 /**************************************************************
2 Problem: 3297
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:1204 ms
7 Memory:2832 kb
8 ****************************************************************/
9
10 var
11 i,j,k,l,m,n:longint;
12 a,b:array[0..2000] of ansistring;
13 s1:ansistring;
14 function check(x:longint;s2:ansistring):boolean;
15 var i:longint;
16 begin
17 for i:=1 to length(s2) do
18 if (s1[x+i]<>'?') and (s1[x+i]<>s2[i]) then exit(false);
19 exit(true);
20 end;
21 begin
22 readln(m,n);
23 readln(s1);
24 for i:=1 to n do readln(a[i]);
25 for i:=1 to m do
26 for j:=1 to n do
27 begin
28 k:=i-length(a[j]);
29 if (k<0) or ((k<>0) and (b[k]='')) then continue;
30 if check(k,a[j]) then
31 begin
32 if (b[i]='') or (b[i]>(b[k]+a[j])) then b[i]:=b[k]+a[j];
33 k:=0;
34 end;
35 end;
36 writeln(b[m]);
37 readln;
38 end. 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-04-13 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录