题目地址

https://codeforces.com/problemset/problem/1446/B

题目大意

定义$S(A,B)=4\cdot LCS(A,B)-\left|A\right|-\left|B\right|$

给两个串串A和B，求AB的两个的子串CD（substring，要求连续），使$S(C,D)$最大。

解法

一开始我想的是先求出lcs数组

再用$res_{i,j}=4\cdot lcs_{i,j}-i-j$记录类似lcs的前缀和。但是后来发现很容易就能推翻，lcs是不能使用这样前缀和的思想的。比如字符串aaa和aaaa，算C为[1,3],D为空结果的就立马会出现问题。

所以不能这样搞。

我们先思考如果这些子串必须都从头开始，即只能从末尾删去字符，该怎么写：

可以得到递推式$dp_{i,j}=dp_{i-1,j-1}+2$如果ai=bi,(增加了长度1,$1\cdot 4-2=2$)

$dp_{i,j}=max(dp_{i-1,j},dp_{i,j-1})-1$如果ai!=bi.

这时候增加一个:也可以从头删去字符，想到怎么写了吗？

就是利用了最大连续子段和的思想：如果在一个位置的$dp_{i,j}<0$则把它归零。

完了。

代码

#include<iostream>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define ll long long
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
ll gcd(ll a,ll b){ while(b^=a^=b^=a%=b); return a;}
string a,b;
int n,m;
const int MAXN = 5005;
int dp[MAXN][MAXN];
int res;
void solve(){
    res = 0;
    cin>>n>>m;
    cin>>a>>b;
    rep(i,1,n){
        rep(j,1,m){
            if(a[i-1]==b[j-1]) dp[i][j] = dp[i-1][j-1]+2;
            else dp[i][j] = max(dp[i-1][j],dp[i][j-1])-1;
            dp[i][j] = max(dp[i][j],0);
            res = max(res,dp[i][j]);
        }
    }
    cout<<res<<endl;
}
int main(){
    solve();
}