题解 P2875 【[USACO07FEB]牛的词汇The Cow Lexicon】

· · 题解

看到这道题，首先想到的是乘积最大、添加号之类的动态规划，于是便有了一种思路。

设状态

F[i]为要使母串前i位匹配字典，所需删除的最少的字母数。

G[a,b]为母串中使从第a到第b位的子串包含字典中的词最长，所需删除的最少的字母数

状态转移方程

F[i]=Min { F[k] + G[k+1,i] } (0<=k<=i-1)

求F[L]的时间复杂度为O(L^2)，关键在于求G[a,b]。

求G[a,b]只有O(L^2*W)的算法，即枚举每种可能的(a,b)，并对字典中W个单词每个进行匹配，找出包含最长的单词长度为l，G[a,b]=b-a+1-l。

有两组数据会超时。

在上述算法的基础上，会发现大量的枚举是冗余的。我们不改变状态，改变状态转移策略即可，正向递推。

由当前状态F[i]向后可以直接推出，F[i+1]，如果F[i+1]<F[i]+1。另外从第i位开始向后找到序列，使该序列包含字典中的某个单词，序列长度-单词长度就是应当删除的字母数量，记为Space，序列的末尾记为Pos，则有F[Pos]=F[i]+Space，如果F[i]+Space<F[Pos]。

状态转移方程

F[Pos]=Min{ F[i]+Space , F[Pos] }

F[i+1]=Min{ F[i+1] , F[i]+1 }

时间复杂度为O(L^2*W)

 #include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
FILE *in = fopen("lexicon.in", "r"), *out = fopen("lexicon.out", "w");
char data[2000];
char words[2000][100];
int w,n;
int best[2001];
void tryword(int pos, int wnum)
 {
    int i,p=pos,t=0;
    for (i=0;i<strlen(words[wnum]);i++)
    {
        while (data[p]!=words[wnum][i])
        {
            p++;t++;
            if (p>=n) return;
        } p++;
    }
    if (best[pos]+t<best[p]) best[p]=best[pos]+t;
}
int main(void)
 {
    int i,j;
    fscanf(in,"%i %i",&w,&n);
    i=0; char c;
    for (i=0;i<n;i++)
    {
        fscanf(in,"%c",&c);
        while (!isalpha(c)) fscanf(in,"%c",&c);
        data[i]=c;
    } data[i]='\0';
    fscanf(in,"%c",&c);
    for (i=0;i<w;i++) fscanf(in,"%s",&words[i][0]);
    for (i=0;i<=n;i++) best[i]=i;
    for (i=0;i<n;i++)
    {
        for (j=0;j<w;j++)
            if (i+strlen(words[j])<=n)
                if (data[i]==words[j][0])
                    tryword(i,j);
        if (best[i]+1<best[i+1]) best[i+1]=best[i]+1;
    }
    fprintf(out,"%i\n",best[n]);
    fclose(in); fclose(out); return 0;
}