poj 3267 The Cow Lexicon(dp)

http://poj.org/problem?id=3267

题意：给出一个由m个字符组成的单词和n个单词表，问至少删除多少个字母使这个单词才能由下面的单词表中的单词组成；

browndcodw 中删除两个d后由brown 和 cow 组成；

思路：从最后一个字母开始匹配，先初始化,dp[m] = 0，假使当前字母不能匹配，则dp[i] = dp[i+1] + 1;然后，遍历单词表中每个单词，如果有单词的首字母与当前字母相同，那么该单词有可能和这个字母以后的单词匹配，经判断后若能匹配，就算出匹配成功要删除的字母个数，我的是(cur-i)-len[j]，取dp[i] 和 dp[cur]+(cur-i)-len[j] 的较小者

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main()
{
	int n,m;
	char s[310],dic[610][30];
	int len[610];
	int dp[310];

	scanf("%d %d",&n,&m);
	scanf("%s",s);
	for(int i = 0; i < n; i++)
	{
		scanf("%s",dic[i]);
		len[i] = strlen(dic[i]);
	}
	
	dp[m] = 0;
	for(int i = m-1; i >= 0; i--)	//从最后一个开始匹配
	{
		dp[i] = dp[i+1]+1;	//初始化，该字符要删

		for(int j = 0; j < n; j++)
		{
			if( dic[j][0] == s[i] && (m-i) >= len[j]) //遍历单词表找到起始位置与i字符相同的单词
			{
				int cur = i+1;//从各自下一个字符开始匹配
				int cnt = 1;
				while(s[cur] && dic[j][cnt])
				{
					if(s[cur++] == dic[j][cnt])
						cnt++;
				}

				if(cnt == len[j])	//当单词表中的该单词被匹配完全，再计算要删除的数。如果没有被匹配完全，不用考虑
					dp[i] = min(dp[i], dp[cur]+(cur-i-len[j]));//cur-i-len[j] 为从当前字符i到匹配完全后的cur之间要删除的个数
			}
		}
	}
	printf("%d\n",dp[0]);
	return 0;

}

poj 3267 The Cow Lexicon(dp)

原文：http://blog.csdn.net/u013081425/article/details/19813829