首页 > 代码库 > 【BZOJ】3214: [Zjoi2013]丽洁体

【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}$


 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 #include<map> 9 using namespace std;10 #define maxn 10010011 #define llg long long 12 #define inf (llg)1e1613 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);14 llg n,m,ans,sum,g[maxn],f[maxn];15 16 llg lena,lenb,lenc,a[maxn],b[maxn],c[maxn],s[maxn];17 vector<llg>p[20000000];18 19 void get_(llg *a,llg &n)20 {21     llg x=0; char ch=getchar();22     for (; ch!=\n; ch=getchar())23         if (ch>=a && ch<=z) x=x*27+ch-a+1; else24             if (x){ a[++n]=x; x=0; }25     if (x) a[++n]=x;26 }27 28 int main()29 {30     yyj("ti");31     get_(s,n);32     get_(a,lena); 33     get_(b,lenb);34     get_(c,lenc);35     llg l=0,r=n+1;36     for (llg i=1;i<=lena;i++)37     {38         l++;39         while (a[i]!=s[l]) l++,sum++;40     }41     for (llg i=lenc;i>=1;i--)42     {43         r--;44         while (s[r]!=c[i]) r--,sum++;45     }46     l++; r--;47     for (llg i=1;i<=lenb;i++) p[b[i]].push_back(i);48     for (llg i=0;i<=lenb;i++) g[i]=inf;49     ans=inf;50     for (llg i=l;i<=r;i++)51     {52         llg w=p[s[i]].size();53         for (llg k=w-1;k>=0;k--)54         {55             llg x=p[s[i]][k];56             if (x==0) continue;57             if (x==1) {f[1]=i; g[1]=0;}58             else59             {60                 if (f[x-1])61                 {62                     f[x]=i; g[x]=g[x-1]+i-f[x-1]-1;63                 }64             }65             ans=min(ans,g[lenb]);66         }67     }68     cout<<ans+sum;69     return 0;70 }

 

【BZOJ】3214: [Zjoi2013]丽洁体