2020 Multi-University Training Contest 2---- HDU--6774、String Distance（dp）

题目链接

题面：

题意：
定义两个符串的距离为执行添加 / 删除操作（可以对于任意一个字符串进行操作）直到两个串相等的最小操作数。

给定一个串 $A$A，和一个串 $B$B，每次询问 $A[l,r]$A[l,r]与 $B$B 的距离。
其中 $len\left(A\right)\le 1e5,len\left(B\right)\le 20$len(A)≤1e5,len(B)≤20

题解：
（一）
首先可以知道，两个串 $S$S 和 $T$T 距离 $dis(S,T)=len\left(S\right)+len\left(T\right)-2\ast lcs(S,T)$dis(S,T)=len(S)+len(T)−2∗lcs(S,T)
两个串的长度和-两倍的最长公共子序列长度。

主要是 $dp\left[i\right]\left[j\right]$dp[i][j]表示与 $B\left[\mathrm{1...}i\right]$B[1...i]的公共子序列长度达到 $j$j的 $A\left[l...r\right]$A[l...r]的最短的前缀长度。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxp=1100;
const int maxm=500100;
const int up=100000;

char a[maxn],b[maxn];
int nt[maxn][26],dp[25][25];

int main(void)
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%s%s",a+1,b+1);
        int n=strlen(a+1);
        int m=strlen(b+1);

        for(int i=0;i<26;i++)
            nt[n][i]=n+1;
        for(int i=n-1;i>=0;i--)
        {
            for(int j=0;j<26;j++)
                nt[i][j]=nt[i+1][j];
            nt[i][a[i+1]-'a']=i+1;
        }

        int q,l,r;
        scanf("%d",&q);
        for(int k=1;k<=q;k++)
        {
            scanf("%d%d",&l,&r);
            for(int i=0;i<=m;i++)
                for(int j=0;j<=i;j++)
                    dp[i][j]=inf;
            dp[0][0]=l-1;
            for(int i=0;i<m;i++)
            {
                for(int j=0;j<=i;j++)
                {
                    dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
                    if(dp[i][j]<r) dp[i+1][j+1]=min(dp[i+1][j+1],nt[dp[i][j]][b[i+1]-'a']);
                }
            }
            int len=0;
            bool flag=true;
            for(int i=m;i>=0;i--)
            {
                for(int j=i;j<=m;j++)
                {
                    if(dp[j][i]<=r)
                    {
                        len=i;
                        flag=false;
                        break;
                    }
                }
                if(!flag) break;
            }
            printf("%d\n",r-l+1+m-2*len);
        }
    }
    return 0;
}

（二）：
$dp\left[i\right]\left[j\right]\left[k\right]表示A串匹配到i，B串匹配到j，且匹配长度为k时，在A串中最晚的起始位置$dp[i][j][k]表示A串匹配到i，B串匹配到j，且匹配长度为k时，在A串中最晚的起始位置。
查询时，只需要在 $dp\left[r\right]\left[j\right]\left[k\right]中查询dp\left[r\right]\left[j\right]\left[k\right]>=l的最大k$dp[r][j][k]中查询dp[r][j][k]>=l的最大k。
时间复杂度 $O\left(\right(n+q\left)m^2\right)$O((n+q)m2)

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxp=1100;
const int maxm=500100;
const int up=100000;

char a[maxn],b[maxn];
int dp[maxn][21][21];

int main(void)
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%s%s",a+1,b+1);
        int n=strlen(a+1);
        int m=strlen(b+1);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                for(int k=1;k<=j;k++)
                {
                    dp[i][j][k]=0;
                    if(a[i]==b[j])
                    {
                        if(k==1) dp[i][j][k]=i;
                        else dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-1]);
                    }
                    if(k<i&&k<j) dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]);
                    if(k<i) dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
                    if(k<j) dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k]);
                }
            }
        }
        int q,l,r;
        scanf("%d",&q);
        for(int p=1;p<=q;p++)
        {
            scanf("%d%d",&l,&r);
            int pos=0;
            for(int i=1;i<=m;i++)
            {
                for(int j=i;j<=m;j++)
                {
                    if(dp[r][j][i]>=l)
                    {
                        pos=i;
                        break;
                    }
                }
            }
            printf("%d\n",r-l+1+m-2*pos);
        }
    }
    return 0;
}