poj 3267 The Cow Lexicon（dp）

题意：给定一个字符串，又给n个单词，求最少删除字符串里几个字母，能匹配到n个单词里
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<stack>
 6 #include<queue>
 7 #include<iomanip>
 8 #include<cmath>
 9 #include<algorithm>
10 using namespace std;
11 
12 char s[700][400];
13 int min_n(int a,int b)
14 {
15     return a>b?b:a;
16 }
17 int main()
18 {
19     int n,m,i,j,d[400],pm,pd,len;   //d【i】表示从i到m 最少需要删多少字母
20     char str[400];
21     while(cin>>n>>m)
22     {
23         cin>>str;
24         for(i=0; i<n; i++)
25             cin>>s[i];
26         d[m] = 0;
27         for(i=m-1; i>=0; i--)  //从后向前
28         {
29             d[i]=d[i+1]+1;         //先做最坏的初始化
30             for(j = 0; j < n; j++)  //从0到n挨个找
31             {
32                 len = strlen(s[j]);
33                 if(str[i]==s[j][0]&&len <= (m-i))
34                 {
35                     pm = i;
36                     pd=0;
37                     while(pm<m)    
38                     {
39                         if(str[pm++]==s[j][pd])  //只加str,相同的话，s++;
40                             pd++;
41                         if(pd==len)        //说明是子串
42                         {
43                             d[i]=min(d[i],d[pm]+pm-i-len);  //状态转移方程
44                             break;
45                         }
46                     }
47                 }
48             }
49         }
50         cout<<d[0]<<endl;
51     }
52     return 0;
53 }