3297: [USACO2011 Open]forgot

3297: [USACO2011 Open]forgot

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 69  Solved: 51

[Submit][Status][Discuss]

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

Silver

题解:看了半天一直还在想着怎么套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.    

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

使用RSQL实现端到端的动态查询

RSQL(RESTful Service Query Language)是Feed Item Query Language (FIQL) 的超集,是一种REST...

910
来自专栏Android 研究

APK安装流程详解14——PMS中的新安装流程上(拷贝)补充

mContext.enforceCallingOrSelfPermission(android.Manifest.permission.INSTALL_PACK...

3721
来自专栏JAVA后端开发

JAVA实现编写平台代码生成器

[项目中经常写CRUD,但实际这些工作,我觉得如果有一个完整的代码规范,完全可以自动生成,加快开发效率. 代码生成器技术原理不复杂,一般就是写好一个模板生成一...

1K2
来自专栏ImportSource

微服务弹性框架hystrix-javanica详解(上)

Java语言相比其他语言有一些比较great的优点,那就是反射(refleaction)和注解(annotation)。 几乎所有的流行框架比如Spring, ...

51310
来自专栏A周立SpringCloud

Spring Cloud Edgware新特性之八:Zuul回退的改进

Spring Cloud Edgware对Hystrix回退的逻辑进行了一些改进。本文将信息探讨新旧版本的回退操作,并分析的原因及改进后的优势。 Dalston...

2976
来自专栏A周立SpringCloud

Spring Cloud限流详解(附源码)

在高并发的应用中,限流往往是一个绕不开的话题。本文详细探讨在Spring Cloud中如何实现限流。 在 Zuul 上实现限流是个不错的选择,只需要编写一个过滤...

6077
来自专栏androidBlog

Android AIDL 传递对象(Parceable)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/de...

832
来自专栏小灰灰

RabbitMQ基础教程之Spring&JavaConfig使用篇

2457
来自专栏Java 源码分析

SpringBoot 笔记(十一):Servlet容器

2632
来自专栏along的开发之旅

Mac os 下打开java内存分析工具 mat

版权声明:欢迎传播,请标明出处。 https://blog.csdn.net/u201011221/article/details/8305...

8033

扫码关注云+社区

领取腾讯云代金券