【0】题解：AT_past202112_h 最長非共通部分列【最长公共子序列】【动态规划】

ExFish · 2025-01-15 21:20:53 · 题解

又发现了一道有趣的题。

我们发现这题让我们求最长非公共子序列。

我们先回忆最长公共子序列。

设 f_{i,j} 是分别处理到这两个位置的答案。

这时要是 a_i=b_j，那么 f_{i,j}=\max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+1)。

否则，f_{i,j}=\max(f_{i-1,j},f_{i,j-1})。

那么，我们可以将条件从 a_i=b_j 变成 a_i\neq b_j，来完成这题。

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
#define int long long
int n,m,a[N],b[N],f[N][N];
string s,t;
signed main(){
    cin>>s>>t;n=s.size();m=t.size();
    for(int i=1;i<=n;i++)a[i]=s[i-1]-'a';
    for(int j=1;j<=m;j++)b[j]=t[j-1]-'a';
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]!=b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout<<f[n][m];
    return 0;
}