3297: [USACO2011 Open]forgot

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 189  Solved: 126
[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

思路:最开始在想AC自动机,然后在自动机上跑DP,会出现空间不足,以及没有高效办法求最小字典序的问题。

然后发现可以用O(N*M*L)的背包来写。但是写起来可能比较麻烦,一下别人的代码,还真是。        巧妙的是,如果我们直接用string的话,代码写起来非常方便,比较大小也直接比较。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
string c,s[maxn],dp[maxn];int N,M,L[maxn];
bool check(int t,int p)
{
rep(i,,L[p]-) if(c[i+t]!='?'&&c[i+t]!=s[p][i]) return false;
return true;
}
int main()
{
cin>>N>>M>>c;
rep(i,,M) cin>>s[i],L[i]=s[i].length();
rep(i,,N) {
rep(j,,M){
if(i<L[j]||(i-L[j]!=&&dp[i-L[j]]=="")) continue;
if(check(i-L[j],j))
if(dp[i]==""||dp[i-L[j]]+s[j]<dp[i]) dp[i]=dp[i-L[j]]+s[j];
}
}
cout<<dp[N]<<endl;
return ;
}
05-11 22:23