【BZOJ】3214: [Zjoi2013]丽洁体

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3214

字符串长度最大不超过$5$直接$HASH$起来

首先在$T$中考虑找到最前的一个包含$A$的子序列，找到最后的一个包含$C$的子序列,直接贪心的确定了$A,C$的位置。

在剩下的区间内$DP$出最合适的$B$的位置。

我们要找到一个区间${[l,r]}$使得$B$是它的子序列，显然应该最小化$r-l$。

令$F[i]$表示$B$中第$i$单词最晚出现的位置。

$g[i]$表示$B$中第$i$单词已经出现过了之后最少要删除多少个单词(答案)。

假设当前在T中的第$i$个单词是B中的第$x$个。

如果$x=1$:${f[1]=1,g[1]=0}$

如果${f[x-1]!=0}$(即出现过了)：${f[x]=i,g[x]=g[x-1]+i-f[x-1]-1}$

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<map>

 using namespace std;

 #define maxn 100100

 #define llg long long

 #define inf (llg)1e16

 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

 llg n,m,ans,sum,g[maxn],f[maxn];

 llg lena,lenb,lenc,a[maxn],b[maxn],c[maxn],s[maxn];

 vector<llg>p[];

 void get_(llg *a,llg &n)

 {

     llg x=; char ch=getchar();

     for (; ch!='\n'; ch=getchar())

         if (ch>='a' && ch<='z') x=x*+ch-'a'+; else

             if (x){ a[++n]=x; x=; }

     if (x) a[++n]=x;

 }

 int main()

 {

     yyj("ti");

     get_(s,n);

     get_(a,lena);

     get_(b,lenb);

     get_(c,lenc);

     llg l=,r=n+;

     for (llg i=;i<=lena;i++)

     {

         l++;

         while (a[i]!=s[l]) l++,sum++;

     }

     for (llg i=lenc;i>=;i--)

     {

         r--;

         while (s[r]!=c[i]) r--,sum++;

     }

     l++; r--;

     for (llg i=;i<=lenb;i++) p[b[i]].push_back(i);

     for (llg i=;i<=lenb;i++) g[i]=inf;

     ans=inf;

     for (llg i=l;i<=r;i++)

     {

         llg w=p[s[i]].size();

         for (llg k=w-;k>=;k--)

         {

             llg x=p[s[i]][k];

             if (x==) continue;

             if (x==) {f[]=i; g[]=;}

             else

             {

                 if (f[x-])

                 {

                     f[x]=i; g[x]=g[x-]+i-f[x-]-;

                 }

             }

             ans=min(ans,g[lenb]);

         }

     }

     cout<<ans+sum;

     return ;

 }

巴特西

【BZOJ】3214: [Zjoi2013]丽洁体

最新文章

热门文章