2020年HDU多校第二场 1012 String Distance(序列自动机,dp)

2020年HDU多校第二场 1012 String Distance(序列自动机,dp)

String Distance

题意:给两个字符串,第一个很长,第二个很短,q次询问每次给一个l,r问操作多少次使第一串的l到r与第二串相等,每次操作选择两串其1在任意位置增加元素或删除元素;

题解:首先很容易想到增加操作是没有必要的,因为我可以在某字符串增加必然可以在另一串相同位置删除,所以很明显就是求两串的最长公共子序列,普通的最长公共子序列是写不了的,因为他给的l的限制,我想预处理出所有dp的话,时间与空间都不够,我们发现,第二个字符串的长度特别短,所以可以用序列自动机对第一个字符串进行降维打击,然后每次询问进行一次dp既可,O(20*20)。dp的话用记忆化搜索会好写很多,可惜HDU卡的太死了,搜索写法超时,这里给上递推式的写法。

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1e9+7;
int m,len,t,n,q,g[100007][30],dp[27][27],l,r;
char s1[100007],s2[100007];
int solve(){
    for(int i=0;i<=m;i++){
        for(int j=0;j<=m;j++){
            dp[i][j]=100006;
        }
    }
    for(int i=0;i<=m;i++)dp[i][0]=l;
    int ans=0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=i;j++){
            dp[i][j]=dp[i-1][j];
            dp[i][j]=min(dp[i][j],g[dp[i-1][j-1]][s2[i]-'a']+1);
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=i;j++){
            if(dp[i][j]<=r+1){
                ans=max(ans,j);
            }
        }
    }
    return ans;
}
void init(){
    memset(g,maxn,sizeof(g));
}
int main(){
    scanf("%d",&t);
    while(t--){
        init();
        scanf("%s%s",s1+1,s2+1);
        len=strlen(s1+1);
        m=strlen(s2+1);
        for(int i=0;i<=25;i++)g[len+1][i]=1e9;
        for(int i=len;i>=1;i--){
            for(int j=0;j<=25;j++){
                g[i][j]=g[i+1][j];
            }
            g[i][s1[i]-'a']=i;
        }
        scanf("%d",&q);
        while(q--){
            scanf("%d%d",&l,&r);
            printf("%d\n",m+r-l+1-2*solve());
        }
    }
}
上一篇:2020.2.19GDUT寒假训练排位赛1-E


下一篇:L2-023 图着色问题