666

focus_aurora · 2023-10-10 21:50:30 · 题解

题目大意

给出两个长度在 5000 以下且完全由英文小写字母组成的字符串 s 和 t，请从 s 中依次挑出若干个字母连成字符串 s'，并从 t 中依次挑出若干个字母连成字符串 t'（都可以不连续，但必须按顺序挑；两个子串长度相等）。现在请求出满足下面条件的 i 的最大值，使得：存在至少一对 s' 和 t'，它们对应位上共有 i 个字母不相同。

题目思路

显然，这是一道 LCS 变种问题（ 最长不公共子序列 ），我们可以用可爱的 DP 来解决。DP 的三要素是：状态，状态转移方程，初始化。初始化非常简单，为 0 即可。定义状态是 v 数组代表 A 和 B 的最长不公共子序列，接下来我们讨论一下如何写状态转移方程。如果 {A_i}={B_j} 的话，那么 {f_i}_j 就会等于他前一个最长的不公共上升子序列，即求 {v_i}_{j-1} 和 {v_{i-1}}_j 的最大值；否则的话我们就让目前最长的非公共上升子序列的长度加一。在每次，我们可以记录一个 maxx 来记录每次的最大值，最后输出 maxx 即可。

好了，话不多说，这是一道非常经典的 DP 问题，是最长上升子序列的演化。下面再展示一下代码。

#include<iostream>
#include<cstdio>
using namespace std;
int v[5005][5005],maxx;
int main(){
    string a,b;
    cin>>a>>b;
    for(int i=0;i<a.size();i++){
        for(int j=0;j<b.size();j++){
            if(a[i]==b[j]){
                v[i+1][j+1]=max(v[i+1][j],v[i][j+1]);
            }
            else{
                v[i+1][j+1]=v[i][j]+1;
            }
            maxx=max(maxx,v[i+1][j+1]);
        }
    }
    cout<<maxx;
    return 0;
}