POJ 3267 The Cow Lexicon

  这道题目看了我很久。

     题意：给你一个主串，和一些单词，问你在主串中至少删除几个字母，是的剩下的都是由给出的单词组成。

   分析：这道题想了我老久，因为我也是在对DP的探究之中。对于主串str,在i的位子上有两个决策：删除，不删除。不删除的话必须在字典当中要有与之匹配的单词，删除的话那么dp[i]= dp[i-1] + 1.不删除则必须分析，如果 acorw 做到w时，假设有一个单词cow可以与之匹配，那么就在str中往回找直到找到了整个单词cow, str此时停留在a位子上，那么dp[i] = dp[j] + ll ( ll 代表 j 到 i要删除的字符数 )。得到这个状态方程就解决了。

代码：

[cpp] 
#include<iostream> 
#include<algorithm> 
#include<cmath> 
using namespace std;  
int w,l,dp[305]; 
char str[305],dict[601][305]; 
int Fn(int pt) 
{ 
    int k,i,j,mim,len; 
    mim=305; 
    for( i=0;i<w;i++){ 
         len=strlen(dict[i]); 
         if( str[pt]==dict[i][len-1]&&len<=pt+1){ //以此字符结尾的单词  
              
             for( j=pt,k=len-1; j>=0&&k>=0;j--)   
                  if( str[j]==dict[i][k]) 
                       k-- ;  
                       
             if( k==-1){ 
                 if(j==-1) mim=min(mim,pt-j-len);  //当str也查找完了就直接返回要删除的长度  
                 else mim=min(mim,dp[j]+pt-j-len); 
             } 
         } 
    } 
   // cout<<mim<<endl; 
    return mim;                            
} 
int main() 
{ 
    int i; 
    while( scanf("%d%d",&w,&l)!=EOF){ 
           memset(dp,0,sizeof(dp)); 
           scanf("%s",str); 
           for(i=0;i<w;i++) 
             scanf("%s",dict[i]); 
              
           for( i=0;i<l;i++){ 
                if(i==0) dp[0]=min(1,Fn(0)); //单独做，害怕字典当中出现长度为1的单词。  
                else dp[i]=min(dp[i-1]+1,Fn(i));    
           } 
            
           printf("%d/n",dp[l-1]); 
    } 
    return 0; 
}