题目描述
发生了这么多,贝茜已经忘记了她 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"。
给你字典,贝西记得的字母,请找到她的密码。如果有一个以上的密码是可能的,找到字典序最前的。
输入
* 第 1 行:两个空格分隔的整数:L 和 NW
* 第 2 行:一个字符串,长度为 L:P
* 第 3..N+2W 行:第 I+2 行包含在字典中的第 i 个字:W_i
输出
* 第 1 行:密码
样例输入
15 6
a??l?ban???????
apple
cow
farmer
banana
bananas
pies
样例输出
applebananapies
题解
坑爹的类背包 dp
设 f[i] 为前 i 长度时字典序最小的字符串。
状态转移方程显然是 f[i]=min{f[i-len[j]]+a[j]}。
然后就是各种判定。
最坑爹的就是 c++ 的 string,头一次用,一脸懵逼,调了半天。
然后代码也很丑,凑合着看吧。
- 1#include 2#include 3#include < string > 4 using namespace std;
- 5 char str[1010],
- w[1010][30],
- ans[1010];
- 6 int len[1010];
- 7 string f[1010],
- a[1010];
- 8 bool judge(int i, int j) 9 {
- 10 int k;
- 11
- for (k = 1; k <= len[j]; k++) 12
- if (str[i - len[j] + k] != ' ? ' && str[i - len[j] + k] != w[j][k]) 13
- return 0;
- 14
- return 1;
- 15
- }
- 16 int main() 17 {
- 18 int n,
- m,
- i,
- j;
- 19 scanf("%d%d%s", &n, &m, str + 1);
- 20
- for (i = 1; i <= m; i++) 21 scanf("%s", w[i] + 1),
- len[i] = strlen(w[i] + 1),
- a[i] = w[i] + 1;
- 22
- for (i = 1; i <= n; i++) 23
- for (j = 1; j <= m; j++) 24
- 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])) 25 f[i] = f[i - len[j]] + a[j];
- 26 printf("%s\n", f[n].c_str());
- 27
- return 0;
- 28
- }
来源: http://www.bubuko.com/infodetail-1946841.html