首页 > 代码库 > POJ 3267 The Cow Lexicon
POJ 3267 The Cow Lexicon
http://poj.org/problem?id=3267
题意：给出一个序列和w个单词，计算至少需要删除多少个单词才能使该序列正好由给出的单词组成。
思路：虽说我知道这道题要用动态规划来做，但是转移方程实在是写不出来，还是依靠了别人的解题报告。
我们设dp(i)代表的是从i~L这部分序列中最少所要删除的单词数，初始化dp[L]=0。状态转移方程如下：
第一个很好理解，就是在不能匹配的情况下，在上一个的基础上多删除一个，也就是删除新加入的单词。
第二个有点复杂，len就是单词的长度，pm相当于是指向序列的指针，pm-i代表的是包含当前单词的序列的长度，因为当中可能还掺杂着别的一些单词，pm-i-len代表的就是多余单词的个数，也就是需要删除个数（比如说，当前序列为codw，比较单词为cow，pm-i=4，pm-i-len=1，也就是要删除d这一个多余的单词）。dp[pm]显然就是序列为pm~L时最少所要删除的单词数。
最后只要输出dp[0]就可以了。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<string> 5 using namespace std; 6 7 char words[605][30]; 8 char mess[305]; 9 int dp[305];10 11 int main()12 {13 //freopen("D:\\txt.txt", "r", stdin);14 int W, L;15 while (cin >> W >> L && W && L)16 {17 cin >> mess;18 for (int i = 0; i < W; i++)19 {20 cin >> words[i];21 }22 dp[L] = 0;23 for (int i = L - 1; i >= 0; i--)24 {25 dp[i] = dp[i + 1] + 1; //无法匹配时需要删除的字符数，先记录一下最坏情况26 for (int j = 0; j < W; j++)27 {28 int len = strlen(words[j]);29 if (len <= L - i && words[j][0] == mess[i]) //单词长度不能大于i~L字段的长度并且首字母得相同30 {31 int p1 = i;32 int p2 = 0;33 34 while (p1 < L)35 {36 if (mess[p1] == words[j][p2])37 {38 p1++;39 p2++;40 }41 else p1++;42 if (p2 == len)43 {44 dp[i] = min(dp[i], dp[p1] + p1 - i - len);45 break;46 }47 }48 }49 50 }51 52 }53 cout << dp[0] << endl;54 }55 return 0;56 }
POJ 3267 The Cow Lexicon
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。