bzoj3297[USACO2011 Open]forgot(dp + string)
2024-08-31 01:54:53
3297: [USACO2011 Open]forgot
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 137 Solved: 94
[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
a??l?ban???????
apple
cow
farmer
banana
bananas
pies
Sample Output
applebananapies
HINT
Source
/*
f[i]为前i长度时字典序最小的字符串。
状态转移方程显然是f[i]=min{f[i-len[j]]+a[j]}。
代码丑,得悟......
*/
#include<iostream>
#include<cstdio>
#include<cstring> #define N 1010 using namespace std;
char str[N],w[N][],ans[N];
int len[N];
string f[N],a[N]; bool judge(int i,int j)//判断方当前字符串行不行
{
for(int k=;k<=len[j];k++)
{
if(str[i-len[j]+k]!='?' && str[i-len[j]+k]!=w[j][k])
return ;
}
return ;
} int main()
{
int n,m,i,j;
scanf("%d%d%s",&n,&m,str+);
for(int i=;i<=m;i++) scanf("%s",w[i]+),len[i]=strlen(w[i]+),a[i]=w[i]+;
for(int i=;i<=n;i++) for(int j=;j<=m;j++)
{
if(len[j]<=i && (i-len[j]==||f[i-len[j]]!="") && judge(i , j) && (f[i]==""||f[i]>f[i-len[j]]+a[j]))
f[i]=f[i-len[j]]+a[j];
}
printf("%s\n" , f[n].c_str());
return ;
}
最新文章
- php+mysql+apache+nginx
- Adaptive Placeholder – 自适应的占位符效果
- confluence的安装、备份和恢复(wiki)
- JDK中的设计模式
- java 利用spring JavaMailSenderImpl发送邮件,支持普通文本、附件、html、velocity模板
- 配置<;authorization>;节(配置文件)
- 比较两个目录中的文件 diff -rq
- Guava: 事件总线EventBus
- Atmel Studio 6.0 重新安装
- acm位运算应用 搜索
- https://hub.docker.com/
- url 编码方法
- 数学概念——E 期望(经典问题)
- 【卷一】正则四 |>; 练习
- 关于xmlHttp.status最新统计
- 夏令营讲课内容整理 Day 2.
- SQL server 2012安装中出现的INSTALLSHAREDDIR 和 INSTALLSHAREDWOWDIR 参数具有相同的值问题
- npm ERR! Unexpected end of JSON input while parsing near...错误
- IDEA远程连接Hadoop
- 一种导致 emwin 中 EDIT 控件不显示的情况