poj-3267-The Cow Lexicon-dp
题意：给你一个字符串，做为被查字符串。
然后给你一系列的字符串，作为字典。
然你从被查字符串中去除掉字典中含有的字符串，可以是不连续的~~
求：被查字符串最小剩下多少个字符。
做法：
dp[i]代表第i字符后面的字符去除掉字典后剩下几个字符。
dp[i]=min（dp[i]，dp[i+1]+1,dp[k+1]+k+1-i-lens);
k代表从第i个字符，往后走，可以找到的一个字典中有的字符串的结束。
lens代表这个字符串的长度。
注意：
dp题目无注意，找好状态方程就好了。
还是有一点需要注意，i后面有可能有好多字符串，所以每比较出来一个字符串，都要min一下。
[html]
#include<iostream>
#include<stdio.h>
#include<string.h>
#define MAXS 999999
using namespace std;
int min(int a,int b,int c)
{
// printf("%d %d %d\n",a,b,c);
int d=a;
if(a>b)
d=b;
if(d>c)
d=c;
return d;
}
int main()
{
int w,l,i,j,k;
char str[1001];
char dian[601][30];
cin>>w>>l;
getchar();
gets(str);
for(i=0;i<w;i++)
{
gets(dian[i]);
}
int dp[301];
for(i=0;i<301;i++)
{
dp[i]=MAXS;
}
int lens;
dp[l]=0;
int x2=0;
for(i=l-1;i>=0;i--)
{
for(j=0;j<w;j++)
{
dp[i]=min(dp[i],MAXS,dp[i+1]+1);
if(dian[j][0]!=str[i])continue;
lens=strlen(dian[j]);
x2=0;
for(k=i;k<l;k++)
{
if(dian[j][x2]==str[k])
{
x2++;
}
if(x2==lens)break;
}
if(k!=l)
{
dp[i]=min(dp[i],dp[i+1]+1,dp[k+1]+k+1-i-lens);
}
}
//printf("%d %d,%d %d %d\n",j,w,i,k,lens);
// printf("dp[%d]=%d\n",i,dp[i]);
}
printf("%d\n",dp[0]);
return 0;
}
补充：软件开发 , C++ ,
