poj3267 The Cow Lexicon
IAmL
posted @ 2009年4月24日 09:59
in 解题报告
with tags
poj3267 The Cow Lexicon解题报告
, 4400 阅读
最近把黑书中关于dp的部分粗略地看了一下，还是不会做dp的题目，泪奔～～～～～～～不过感觉就或多或少还是有的……
这题我一开始想到的状态表示方法是：d[i]表示0～i的字符串里面最少要删除的字符数。然后写了很久，debug了很久，还是WA。之后上discuss看了一下，发现其实只要逆着看状态，就好写很多。把d[i]表示从i到l-1的字符串里面最少要删除的字符数。
然后状态转移方程是：
f(i) = min{ d+f(k), f(i+1)+1 }。
d:表为匹配单词而删的字符数(如果可以匹配)；
k:表匹配后单词的下一个位置；
d+f(k):表保留第i个位置字符的情况；
f(i+1)+1:表不保留第i个位置字符的情况。
后记：
1.为什么两个状态表示方法的实现会差那么远了？如果d[i]表示0～i的字符串里面最少要删除的字符数，那么状态方程为d[i] = min{d[i - 1] + 1, d[i - len[j] - t] + t}，这里无法确定t的大小，也就是说无法确定究竟从i之前的哪个位置开始匹配字符串。所以这个状态表示不可行。
2.附加一些自己出的数据：
Sample Input
2 6
bbrown
bbrow
brown
1 10
browndcodw
browndcodw
6 10
browndcodw
cow
milk
white
black
brown
farmer
1 5
ddddd
d
Sample Output
1
0
2
0
＝＝＝＝＝＝＝＝＝＝＝分割线＝＝＝＝＝＝＝＝＝＝＝＝＝
#include <iostream>
#include <cstring>
using namespace std;
char dict[601][26], rec[301];
int w, l, d[601], len[601];
/*
d(i) 表示以第i个位置起并保留该位置的字母的字符串匹配时需要删的最少字符数
t:表为匹配单词而删的字符数(如果可以匹配)
*/
int main()
{
int i, j, k, tmp, now, t;
while (cin >> w >> l)
{
scanf("%s", rec);
for (i = 0; i < w; i++)
{
scanf("%s", dict[i]);
len[i] = strlen(dict[i]);
}
memset(d, 0, sizeof(d));
//dp
for (i = l - 1; i >= 0; i--)
{
for (now = 601, j = 0; j < w; j++)
{
if (rec[i] != dict[j][0]) continue;
//匹配
k = 1;
t = 0;
tmp = i + 1;
while (k < len[j] && tmp < l)
{
if (rec[tmp] == dict[j][k]) k++;
else t++;
tmp++;
}
//找出所有符合要求的匹配中的最小值
if (k >= len[j]) now = t + d[tmp] > now ? now : t + d[tmp];
}
//用符合要求的匹配的最小值和d[i+1]+1比较
d[i] = d[i + 1] + 1 > now ? now : d[i + 1] + 1;
}
cout << d[0] << endl;
}
return 0;
}
#include <cstring>
using namespace std;
char dict[601][26], rec[301];
int w, l, d[601], len[601];
/*
d(i) 表示以第i个位置起并保留该位置的字母的字符串匹配时需要删的最少字符数
t:表为匹配单词而删的字符数(如果可以匹配)
*/
int main()
{
int i, j, k, tmp, now, t;
while (cin >> w >> l)
{
scanf("%s", rec);
for (i = 0; i < w; i++)
{
scanf("%s", dict[i]);
len[i] = strlen(dict[i]);
}
memset(d, 0, sizeof(d));
//dp
for (i = l - 1; i >= 0; i--)
{
for (now = 601, j = 0; j < w; j++)
{
if (rec[i] != dict[j][0]) continue;
//匹配
k = 1;
t = 0;
tmp = i + 1;
while (k < len[j] && tmp < l)
{
if (rec[tmp] == dict[j][k]) k++;
else t++;
tmp++;
}
//找出所有符合要求的匹配中的最小值
if (k >= len[j]) now = t + d[tmp] > now ? now : t + d[tmp];
}
//用符合要求的匹配的最小值和d[i+1]+1比较
d[i] = d[i + 1] + 1 > now ? now : d[i + 1] + 1;
}
cout << d[0] << endl;
}
return 0;
}
评论 (0)