首页 > 代码库 > PKU 3267

PKU 3267

题目大意:给定一个字符串和一本字典,问至少需要删除多少个字符才能匹配到字典中的单词序列。PS:是单词序列,而不是一个单词

思路:                                                                   动态规划

主要是知道状态方程的含义:

令dp[i]表示从message中第i个字符开始,到第L个字符(结尾处)这段区间所删除的字符数,初始化为dp[L]=0 (dp[i]的下标从0开始)

从message尾部向头部检索匹配,所以是下面的状态方程:


技术分享 

从程序可以看出,第i个位置到L所删除的字符数,总是先取最坏情况,只有mesg[i]可以匹配dict中单词首字母时才进入第二条方程进行状态优化更新。

第一条方程不难理解,只要弄懂dp[i]的意义就能简单推导

第二条方程难点在dp[pm]+(pm-i)-len

设pm是指向message的指针(其中i表示当前所匹配的单词在message中的起始位置),pd是指向字典的指针

匹配的过程是:

当确认message第i位和某单词的首位吻合时,就开始逐字匹配,字符相同则两个指针同时向后移动一次,否则pd固定,pm移动

当因为pm>L跳出匹配时,说明匹配失败,dp[i]状态不变;当pd==单词长度时,单词匹配成功,进行dp[i]的状态更新优化

显然,匹配成功时,pm-i代表匹配过程中从位置i到pm的区间长度,再减去单词长度len,则得到从i到pm所删除的字符数(pm-i)-len。

又dp[pm]表示从pm到L所删除的字符数从而dp[pm]+(pm-i)-len表示i到L删除的字符数,不难证明这个值一定比dp[i]相等或更优,

因此取min赋值给dp[i],这是本题最难的地方,最后输出dp[0]就可以了。

注意:不能写dp[pm+1]+(pm-i+1)-len表示i到L删除的字符数。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std; 
int main()
{
    int w,l;
    while(cin>>w>>l){
        int *dp=new int[l]; 
        char *mesg=new char[l];
        cin>>mesg;
        string *dict=new string[w];
        for(int i=0;i<w;i++)
            cin>>dict[i];
        dp[l]=0;
        for(int i=l-1;i>=0;i--){
            dp[i]=dp[i+1]+1;
            for(int j=0;j<w;j++){
                int len=dict[j].length();
                if(len<=l-i&&dict[j][0]==mesg[i]){
                    int pm=i,pd=0;
                    while(pm<l){ 
                        if(dict[j][pd]==mesg[pm++])
                             pd++;//不管dict[j][pd]和mesg[pm]是否相等,pm都要++ 
                        if(pd==len){
                            dp[i]=min(dp[i],dp[pm]+pm-i-pd);
                            break;//直接break,因为dp[i]表示的是待删除得最少字符,后面的就不用考虑了 
                        }
                    }
                }
            }
        }
        cout<<dp[0]<<endl;
    }
} 

 

PKU 3267