从今天开始POJ里的一部分类型的题目就一般不放在一起写了

一个是太丑，格式麻烦，第二个是以后的题目难度都有所增大，因此一道题可能就要写蛮长

尤其是DP这一块，以前一直没好好学习，现在从基础的先开始吧

题意：给你一个较长的长度为L的串，以及W个长度较短的串。现在问你要从较长串中删去最少几个字符，才能使得这个串由那些长度较短的串组成。

好，题意有点难懂是吧，可以看一下example

删去那两个d使原串变成browncow，既满足要求

首先这个问题肯定满足从局部最优可以推到全局最优

即设f[i]表示先i个字符中最少要删去多少个字符才满足要求

然后发现f[i]可以从它前面转移：

f[i]=min(f[i-1]+1,f[j]+work(s(j,i),t[k]))(1<=i<=l;0<=j
    
     <=k<=w)
    

其中work表示要对s(j,i)删去几个字符才能使s(j,i)等于t[k]

CODE

#include
    
     #include
     
      using namespace std;const int INF=1e9;int n,m,cnt,f[305];string s,t[605];inline int get(string t,string s){    register int i;    int p=0;    for (i=0;i
      
       >n>>m>>s;    for (i=1;i<=n;++i)    cin>>t[i];    for (i=1,f[1]=1;i<=m;++i,f[i]=f[i-1]+1)    for (j=0;j
      
     
    

但是这样的话时间复杂度爆炸

然后我们很显然地发现，对于一个串，只需要找到在前面第一个包含它的字串然后转移即可，就可以省去枚举j的那一维

CODE

#include
    
     #include
     
      using namespace std;const int INF=1e9;int n,m,cnt,f[305];string s,t[605];inline int min(int a,int b){    return a
      
       >n>>m>>s;    for (i=1;i<=n;++i)    cin>>t[i];    for (i=1,f[1]=1;i<=m;++i,f[i]=f[i-1]+1)    {        for (j=1;j<=n;++j)        {            int p1=i-1,p2=t[j].size()-1;            while (p2>=0&&p1>=0)            {                if (s[p1]==t[j][p2]) --p2; --p1;            }            if (p2<0) f[i]=min(f[i],f[p1+1]+i-p1-t[j].size()-1);        }    }    printf("%d",f[m]);    return 0;}