poj 3267 The Cow Lexicon（dp）

题目：http://poj.org/problem?id=3267

题意：给定一个字符串，又给n个单词，求最少删除字符串里几个字母，能匹配到n个单词里

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<stack>

 #include<queue>

 #include<iomanip>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 char s[][];

 int min_n(int a,int b)

 {

     return a>b?b:a;

 }

 int main()

 {

     int n,m,i,j,d[],pm,pd,len;   //d【i】表示从i到m 最少需要删多少字母

     char str[];

     while(cin>>n>>m)

     {

         cin>>str;

         for(i=; i<n; i++)

             cin>>s[i];

         d[m] = ;

         for(i=m-; i>=; i--)  //从后向前

         {

             d[i]=d[i+]+;         //先做最坏的初始化

             for(j = ; j < n; j++)  //从0到n挨个找

             {

                 len = strlen(s[j]);

                 if(str[i]==s[j][]&&len <= (m-i))

                 {

                     pm = i;

                     pd=;

                     while(pm<m)

                     {

                         if(str[pm++]==s[j][pd])  //只加str,相同的话，s++;

                             pd++;

                         if(pd==len)        //说明是子串

                         {

                             d[i]=min(d[i],d[pm]+pm-i-len);  //状态转移方程

                             break;

                         }

                     }

                 }

             }

         }

         cout<<d[]<<endl;

     }

     return ;

 }