codeforces-#683-D

codeforces-#683-D

十一月 16, 2020

D. Catching Cheaters

  • 题意

给出一个长度为n的字符串S和一个长度为m的字符串T

(n,m<5000)

求4LCS(C,D)-|C|-|D|的最大值 (LCS为最长公共子序列)

其中C为S的任意子串 D为T的任意子串 (均可以为空串)

  • 题解

考虑LCS的dp过程

dp(i,j)表示S串前i位和T串前j位构成的最大公共子序列长度 (不一定包含第i位和第j位)

状态转移有:

1
2
if(S[i]==T[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

本题涉及求LCS 于是思考能否从这个角度进行类似的dp求解

设计dp(i,j)表示取S串第i位字符且取T串第j位字符能构成4LCS(C,D)-|C|-|D|的最大值

状态转移有:

1
2
if(S[i]==T[j]) dp[i][j]=dp[i-1][j-1]+2;
else dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i][j-1])-1);

对于S[i]==T[j]的情况 将这两个字符作为子串C和D的末尾

则根据公式4LCS(C,D)-|C|-|D|对答案产生+2的贡献

对于S[i]!=T[j]的情况 根据公式4LCS(C,D)-|C|-|D|

要么给C串加入S[i]要么给D串加入T[j] 对答案的贡献-1

当这两种情况导致当前的子串C和D得到的答案4LCS(C,D)-|C|-|D|<0

那么将这两个子串C和D舍去 保留之前更新的dp(i,j)

有点类似贪心求解最大子段和的过程：

  • 当某个子段和已经小于0那么没必要将这段子串和加入答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
//#define P pair<ll,ll>
const int Max=5e3+5;
const int Mod=1e9+7;
const int inf=0x3f3f3f3f;

#define __DEBUG__
#ifdef __DEBUG__
#define DeBug(format, ...)                                                                            \
{                                                                                                   \
    fprintf(stdout, "\033[33m[%s:%d] \033[0m" format "",                                            \
    __FUNCTION__ , __LINE__, ##__VA_ARGS__);                                                        \
}
#else
#define DeBug(format,...)
#endif
int dp[Max][Max];
int main(void){
    Turnoff;
    int n,m,ans=0;cin>>n>>m;
    string s,t;cin>>s>>t;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i]==t[j])dp[i+1][j+1]=dp[i][j]+2;
            else{
                dp[i+1][j+1]=max(dp[i+1][j+1],max(dp[i+1][j],dp[i][j+1])-1);
            }
            ans=max(ans,dp[i+1][j+1]);
        }
    }
    cout<<ans<<endl;
}