给出一个字符串和一些单词，让你删除尽可能少的字母在字符串中，使得这些单词可以组成这个字符串。
d[i]=min(d[i],d[k]+cnt)
对于每个i，在0到i的范围内可能存在符合某些单词的序列存在，注意，不是字串，所以枚举每个单词，从后往前匹配，同时计算不同的字母的个数，即删除的个数cnt，k即为匹配之后在字符串中的下标。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <string> #include <cmath> #include <set> using namespace std; const int INF=1e9+100; typedef long long ll; char s1[305],s2[605][30]; int lens2[605]; int d[305]; int main(){ //freopen("out.txt","w",stdout); int n,m; while(scanf("%d %d",&n,&m)!=EOF){ scanf("%s",s1+1); for(int i=0;i<n;i++){ scanf("%s",s2[i]); lens2[i]=strlen(s2[i]); } d[0]=0; for(int i=1;i<=m;i++){ d[i]=d[i-1]+1; for(int j=0;j<n;j++){ int cnt=0,k=i,now=lens2[j]-1; for(;k>=1&&now>=0;k--){ if(s1[k]==s2[j][now]) now--; else cnt++; } if(now==-1){ d[i]=min(d[i],d[k]+cnt); } } } printf("%d\n",d[m]); } return 0; }