[DP 动态规划]poj 3267：The Cow Lexicon

大致题意：

    给出一个长度为l的文本和一个由n个单词组成的字典。求至少从文本中去掉多少个字符才能使得这个文本全部由字典中的单词组成。

 

大致思路：

    DP，转移方程为dp[i]=min(dp[i-1]+1,dp[pos+1]+i-pos-1-tmp);//dp[i]为前i个字符中需要去掉的字符数量。

    转移的示例如下，这里文本是browndcodw 文本是cow，从str[9]开始匹配~~

     b r o w n d c o d w

                       c o    w  //找到一个匹配，并需要剔除一个字母。所以dp[10]可以从dp[6]转化而来。

 

 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[1000];
char word[1000][30];
int dp[1000];
int main(){
    int n,len,i,j,pos,k,tmp;
    while(scanf("%d%d",&n,&len)!=EOF){
        scanf("%s",str);
        for(i=0;i<n;i++){
            scanf("%s",word[i]);
        }
        dp[0]=0;    //前i个字符中包含的非法字符数量
        for(i=1;i<=len;i++){
            dp[i]=dp[i-1]+1;
            for(j=0;j<n;j++){
                tmp=k=strlen(word[j]);
                k-=1;
                pos=i-1;
                while(pos>=0&&k>=0){
                    if(str[pos]==word[j][k]){
                        k--;
                    }
                    pos--;
                }
                if(k<0){      //可以匹配出一个单词
                    dp[i]=min(dp[i],dp[pos+1]+i-pos-1-tmp);
                }
            }
        }
        printf("%d\n",dp[len]);
    }
    return 0;
}