题解 P3333 【[ZJOI2013]丽洁体】

· · 题解

题意：给定字符串序列 \mathtt{T,A,B,C} ，求在 \mathtt T 中最少删几个字符串可以得到序列 \mathtt{A...B...C} 。保证有解。

首先，由于要得到的串开头和结尾要是 \mathtt A 和 \mathtt C，显然在原序列上从前往后匹配第一个包含 \mathtt A 的子序列作为新串开头；以原序列上从后往前匹配第一个包含 \mathtt C 的子序列作为新串结尾一定最优。

于是现在我们将问题变成了如何在开头和结尾之间这一段找一个跨度最小的包含 \mathtt B 的子序列。

按照常规思路我们应该考虑 \mathbf O(n^2) dp，设 f_{i,j} 表示匹配到原序列第 i 个串，匹配了 \mathtt B 中的 j 个串的最小长度，f_{i,j}=1+\begin{cases}\min\{f_{i-1,j},f_{i-1,j-1}\}&T_i=B_j\\f_{i-1,j}&T_i\not=B_j\end{cases}。

然后我们就发现 n\leq50000 直接凉凉。

仔细观察一下数据范围，发现有一句“所有单词长度不超过 5，出现次数不超过 500”。由于每个单词出现次数不超过 500，所以 \mathtt B 的开头最多在原串里出现 500 次，所以我们可以暴力枚举这个串从哪儿开头，复杂度仅有 500\cdot|\mathtt T|，能过。

有由于“单词长度不超过 5”，所以我们可以暴力匹配两个串是否相等，不用哈希。（直接用 string 暴力匹配）

于是这题就彻底沦为了普及组的序列暴力匹配练习题。。。 

#include<cstdio>
#include<string>
const int N=50010;
int n,a,b,c,ans,mn;
std::string sn[N],sa[N],sb[N],sc[N];
void read(int &n,std::string sn[])
{
    char ch;
    do ch=getchar();while(ch<=32);
    for(n=1;;n++)
    {
        do sn[n]+=ch,ch=getchar(); while(ch>32);
        while(ch<=32){if(ch=='\n'||ch==EOF)break;ch=getchar();}
        if(ch=='\n'||ch==EOF)break;//读到换行符就停止
    }
}
int main()
{
    int i,j;
    read(n,sn);read(a,sa);read(b,sb);read(c,sc);//读入
    for(i=j=1;j<=a;i++)
    if(sn[i]==sa[j])++j;//暴力匹配
    ans+=i-1-a;int l=i;
    for(i=n,j=c;j>=1;i--)
    if(sn[i]==sc[j])--j;//暴力匹配
    ans+=n-i-c;int r=i;
    for(;l<=r;l++)
    if(sn[l]==sb[1])
    {
        for(i=l,j=1;j<=b;i++)
        if(sn[i]==sb[j])++j;//暴力匹配
        if(i-1<=r&&mn>i-l-b)mn=i-l-b;
    }
    ans+=mn;
    printf("%d\n",ans);//完
    return 0;
}

ps:各位不要再尝试抄题解了，也建议管理员查一下这题大部分AC代码都一模一样的现象。