关键词:动态规划  字符串 相关题目:[USACO2011 Open]forgot

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&Output

Input 第1行:两个空格分隔的整数:L和NW 第2行:一个字符串,长度为L:P 第3...N+2W行:第I+2行包含在字典中的第i个字:W_i

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<algorithm>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
const int N=1020;
int l,nw,len[N];
char s[N];
string str[N],dp[N];
int main(){
cin>>l>>nw;
scanf("%s",s+1);
rep(i,1,nw) cin>>str[i];
sort(str+1,str+nw+1);

rep(i,1,nw) len[i]=str[i].length();
bool flag;
rep(i,1,l)
rep(j,1,nw){
if(i<len[j]) continue;//长度不足
if(i!=len[j] && dp[i-len[j]]=="") continue;//dp[i-len[j]]不存在
flag=0;
rep(k,0,len[j]-1){
re skd=i-len[j]+k+1;
if(s[skd]!='?' && s[skd]!=str[j][k]){flag=1;break;}//不匹配
}
if(flag) continue;
if(dp[i]=="" || dp[i]>dp[i-len[j]]+str[j])
dp[i]=dp[i-len[j]]+str[j];//更新更优解
}
cout<<dp[l]<<endl;
}
//STL大法好