POJ 3267 The Cow Lexicon DP

传送门：POJ3276

题意：给定一串字符串和多个单词，问最少去掉多少个字母才能使其由给定单词拼出来。  

思路：令dp[i]表示到第i个字母最少去多少个字母，则有(设字符串为s)：

1.若s[i]与某个单词c首字母相同，则dp[i]=min(dp[i]，dp[j]+j-i-strlen(c))

2.若s[i]与所有单词首字母都不同则有dp[i]=dp[i-1]+1

3.初始化dp[n]=0

以上的结论是逆向递推的时候的结论，正向也可以写，不过个人感觉逆向好写也好理解一些。

代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<map>
#define ll long long
#define pi acos(-1)
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int>P;
string s,c[1000];
int dp[303];
int main()
{	
	int w,l;
	scanf("%d%d",&w,&l);
	cin>>s;
	for(int i=0;i<w;i++)cin>>c[i];
	dp[l]=0;
	for(int i=s.length()-1;i>=0;i--)
	{
		dp[i]=dp[i+1]+1;
		for(int j=0;j<w;j++)
		{
			int k=i,m=0;
			if(s[k]==c[j][m]&&s.length()-i>=c[j].length())
			while(1)
			{
				if(k>=s.length()||m>=c[j].length())break;
				if(s[k++]==c[j][m])m++;
				if(m==c[j].length())
				{
					dp[i]=min(dp[i],dp[k]+k-i-(int)c[j].length());
					break;
				}
			}
		}
	}
	printf("%d\n",dp[0]);
    return 0;
}