P8020 [ONTAK2015] Badania naukowe
Coros_Trusds
·
·
题解
更好的阅读体验
# 题目大意
给定三个数字串 $A,B,C$，请找到一个 $A,B$ 的最长公共子序列，满足 $C$ 是该子序列的子串。
# 题目分析
**本题解中数组下标均从 $1$ 开始。**
初见此题，我们对答案毫无头绪，不妨考虑答案是由什么构成的。
我们枚举 $C$ 在 $A,B$ 中的位置，再加上前后各自的最长公共子序列长度。
设 $n,m,k$ 分别表示 $A,B,C$ 序列的长度。
令 $dp1[i][j]$ 表示 $a[1\dots i]$ 和 $b[1\dots j]$ 的最长公共子序列长度，$dp2[i][j]$ 表示 $a[i\dots n]$ 和 $b[j\dots m]$ 的最长公共子序列长度。
我们先处理出 $dp1$ 和 $dp2$，处理步骤见 $\verb!P1439!$。
特别地，当 $C$ 序列的长度为 $0$ 时，答案为 $dp1[n][m]$。（$20$ 分到手了）
好了，现在答案中“前后各自的最长公共子序列长度”求出来了。
------
处理出 $ta$ 和 $tb$ 数组，$ta[i]$ 表示 $C$ 是否在 $a[i\dots n]$ 中出现（不一定连续），如果出现了的话 $ta[i]$ 存储 $C$ 的最后一个元素在 $A$ 中的下标，否则为 $0$。
$tb[i]$ 表示 $C$ 是否在 $b[i\dots m]$ 中出现（不一定连续），如果出现了的话 $tb[i]$ 存储 $C$ 的最后一个元素在 $B$ 中的下标，否则为 $0$。
最后答案即为 $\max\{dp1[i-1][j-1]+k+dp2[ta[i]+1][tb[j]+1]\}(1\le i\le n,1\le j\le m)$。
# 代码
```cpp
const int ma=3e3+5;
int a[ma],b[ma],c[ma];
int ta[ma],tb[ma];
int dp1[ma][ma],dp2[ma][ma];
//dp1[i][j]:LCS(a[1...i],b[1...j])
//dp2[i][j]:LCS(a[i...n],b[j...m])
int n,m,k;
inline void work1()
{
for(register int i=1;i<=n;i++)
{
for(register int j=1;j<=m;j++)
{
if(a[i]==b[j])
{
dp1[i][j]=dp1[i-1][j-1]+1;
}
else
{
dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1]);
}
}
}
if(k==0)
{
printf("%d\n",dp1[n][m]);
exit(0);
}
}
inline void work2()
{
for(register int i=n;i>=1;i--)
{
for(register int j=m;j>=1;j--)
{
if(a[i]==b[j])
{
dp2[i][j]=dp2[i+1][j+1]+1;
}
else
{
dp2[i][j]=max(dp2[i+1][j],dp2[i][j+1]);
}
}
}
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
n=read();Input_Int(n,a);
m=read();Input_Int(m,b);
k=read();Input_Int(k,c);
work1(),work2();
for(register int i=1;i<=n;i++)
{
for(register int j=i,t=1;j<=n;j++)
{
if(a[j]==c[t])
{
t++;
}
if(t>k)
{
ta[i]=j;
break;
}
}
}
for(register int i=1;i<=m;i++)
{
for(register int j=i,t=1;j<=m;j++)
{
if(b[j]==c[t])
{
t++;
}
if(t>k)
{
tb[i]=j;
break;
}
}
}
int ans=-1;
for(register int i=1;i<=n;i++)
{
for(register int j=1;j<=m;j++)
{
if(ta[i]!=0 && tb[j]!=0)//如果没出现就别考虑了
{
ans=max(ans,dp1[i-1][j-1]+k+dp2[ta[i]+1][tb[j]+1]);
}
}
}
printf("%d\n",ans);
return 0;
}
```
# 题外话
各位读者 dalao 如果觉得这篇文章有用不妨点个赞吧qwq。