题目描述
发生了这么多，贝茜已经忘记了她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 <cstdio> 2 #include <cstring> 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 }
【bzoj3297】[USACO2011 Open]forgot
原文：http://www.cnblogs.com/GXZlegend/p/6404740.html