首页 > 代码库 > bzoj3297[USACO2011 Open]forgot(dp + string)

bzoj3297[USACO2011 Open]forgot(dp + string)

2024-10-11 09:23:02   210人阅读

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

Sample Output

applebananapies

HINT

 

Source

Silver

 

/*f[i]为前i长度时字典序最小的字符串。状态转移方程显然是f[i]=min{f[i-len[j]]+a[j]}。代码丑，得悟...... */#include<iostream>#include<cstdio>#include<cstring>#define N 1010using namespace std;char str[N],w[N][30],ans[N];int len[N];string f[N],a[N];bool judge(int i,int j)//判断方当前字符串行不行 {    for(int k=1;k<=len[j];k++)    {        if(str[i-len[j]+k]!=‘?‘ && str[i-len[j]+k]!=w[j][k])         return 0;    }    return 1;}int main(){    int n,m,i,j;    scanf("%d%d%s",&n,&m,str+1);    for(int i=1;i<=m;i++) scanf("%s",w[i]+1),len[i]=strlen(w[i]+1),a[i]=w[i]+1;    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)    {        if(len[j]<=i && (i-len[j]==0||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 0;}

 

bzoj3297[USACO2011 Open]forgot(dp + string)


联系
我们