CF1446B Catching Cheaters（LCS+DP） 1800

题意

题目链接：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;
}