题意
题目链接:Problem - 1446B - Codeforces
前置知识——LCS(最长公共字串),给你两个字符串A,B,你需要分别在其中选择两个字串C,D,使得得分最大,得分计算如下:
4\times LCS(C,D) - |C| - |D|
LCS(C,D)指的是字符串C,D最长公共子串的长度。数据范围1\leq n,m\leq 5000。
思路
一开始是没有思路的,看了题解才恍然大悟,对于得分可以这么理解:
- 如果我在原有基础上,多匹配一个,那么LCS(C,D)会增加1,乘以四只会,贡献是增加4,但是后面的减法呢?每成功匹配一个,|C|和|D|的长度都会增加1
- 如果匹配没有成功,那么我两层循环中,|D|的长度会增加1,这样使得整个值减1
为什么是只有一个,因为每次匹配是哪
s2[j]
与s1[i]
比较,如果匹配失败那么就往下,用s2[j+1]
去比较。所以只有一个。
因此:
1)如果匹配成功,贡献+2;
2)如果匹配失败,贡献-1.
其他跟LCS一模一样,只是正常的LCS里面计算贡献的时候,匹配失败就继承上一次最大的,成功就+1.
代码
inline void Case_Test()
{
cin>>n>>m>>s1>>s2;
s1 = " "+s1;
s2 = " "+s2;
rep(i,1,n)rep(j,1,m)
{
if (s1[i]==s2[j])
f[i][j] = f[i-1][j-1] + 2;//贡献+2
else
f[i][j] = Max(Max(f[i-1][j],f[i][j-1])-1,0);//贡献-1
ans = Max(ans,f[i][j]);//取出现过的最大值
}
cout<<ans;
}
文章评论