首页 > 代码库 > BZOJ3297: [USACO2011 Open]forgot
BZOJ3297: [USACO2011 Open]forgot
3297: [USACO2011 Open]forgot
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 54 Solved: 38
[Submit][Status]
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
Silver
题解:
刚开始写爆搜,写到一半儿发现写不下去了。。。
这题居然是DP,orz。。。
if(check(k+1,j)) { if(f[j]==""||f[i]>f[k]+s[j])f[i]=f[k]+s[j]; }
没想到字符串还能这样比较,orzzzzzzzzz
代码:(copy)
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #include<algorithm> 6 #define pa pair<int,int> 7 #define inf 1000000000 8 #define ll long long 9 using namespace std;10 inline int read()11 {12 int x=0;char ch=getchar();13 while(ch<‘0‘||ch>‘9‘)ch=getchar();14 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}15 return x;16 }17 int p,n;18 int l[1005];19 char ch[1005];20 string a[1005],f[1005];21 bool jud(int st,int x)22 {23 for(int i=0;i<l[x];i++)24 if(ch[st+i]!=‘?‘&&ch[st+i]!=a[x][i])return 0;25 return 1;26 }27 int main()28 {29 p=read();n=read();30 scanf("%s",ch+1);31 for(int i=1;i<=n;i++)cin>>a[i];32 for(int i=1;i<=n;i++)l[i]=a[i].size();33 for(int i=1;i<=p;i++)34 for(int j=1;j<=n;j++)35 {36 int t=i-l[j];37 if(t<0)continue;38 if(t!=0&&f[t]=="")continue;39 if(jud(t+1,j))40 if(f[i]==""||f[i]>f[t]+a[j])f[i]=f[t]+a[j];41 }42 cout<<f[p]<<endl;43 return 0;44 }
BZOJ3297: [USACO2011 Open]forgot
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。