题解：CF49E Common ancestor

hoko · 2025-07-03 15:06:21 · 题解

题目传送门

题目大意

给出两个字符串，给出 n 种转换方式，求出两个字符串通过若干次转换后，能变成的最短的且相同的字符串长度。

思路

注意到 n\le 50，所以我们考虑区间 dp。先预处理出一个 vis_{i,j,k} 表示字符 i 和字符 j 可以转换成字符 k。

我们分别对两个字符串进行区间 dp，我们定义 f_{i,j,z} 表示，字符串的 [i,j] 经过若干次转换后可以变成字符 z。我们枚举 k\in [i+1,j-1]，如果 f_{i,k,x} 为真，并且 f_{k+1,j,y} 为真并且 vis_{x,y,z} 为真，那么 f_{i,j,z} 为真。

假定我们对两个字符串区间 dp 完后的数组分别为 fa 和 fb，那么如何统计答案呢。统计答案时我们用动态规划，定义 dp_{i,j} 表示处理完第一个字符串的前 i 位和第二个字符串的前 j 位后，两个字符串能变成的最短的且相同的字符串长度。我们枚举 x\in[0,i-1] 和 y\in[0,j-1] 如果 fa_{x+1,i,z} 为真并且 fb_{y+1,j,z} 为真，那么 dp_{i,j}=\min(dp_{i,j},dp_{x,y}+1)。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=60;
ll n,m,a[N],b[N],fa[N][N][N],fb[N][N][N],dp[N][N],vis[N][N][N],t;
string s1,s2;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>s1>>s2;
    n=s1.size();
    m=s2.size();
    s1=' '+s1;
    s2=' '+s2;
    for(int i=1;i<=n;i++)a[i]=s1[i]-'a'+1;
    for(int i=1;i<=m;i++)b[i]=s2[i]-'a'+1;
    cin>>t;
    for(int i=1;i<=t;i++){
        char c1,c2,z,x,y;
        cin>>z>>c1>>c2>>x>>y;
        vis[x-'a'+1][y-'a'+1][z-'a'+1]=1;
    }
    for(int i=1;i<=n;i++)fa[i][i][a[i]]=1;
    for(int i=1;i<=m;i++)fb[i][i][b[i]]=1;
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            for(int k=i;k<j;k++){
                for(int x=1;x<=26;x++){
                    for(int y=1;y<=26;y++){
                        for(int z=1;z<=26;z++){
                            if(fa[i][k][x]&&fa[k+1][j][y]&&vis[x][y][z]){
                                fa[i][j][z]=1;
                            }
                        }
                    }
                }
            }
        }
    }
    for(int len=2;len<=m;len++){
        for(int i=1;i+len-1<=m;i++){
            int j=i+len-1;
            for(int k=i;k<j;k++){
                for(int x=1;x<=26;x++){
                    for(int y=1;y<=26;y++){
                        for(int z=1;z<=26;z++){
                            if(fb[i][k][x]&&fb[k+1][j][y]&&vis[x][y][z]){
                                fb[i][j][z]=1;
                            }
                        }
                    }
                }
            }
        }
    }
    for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)dp[i][j]=1e18;
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int x=0;x<i;x++){
                for(int y=0;y<j;y++){
                    for(int z=1;z<=26;z++){
                        if(fa[x+1][i][z]&&fb[y+1][j][z]){
                            dp[i][j]=min(dp[i][j],dp[x][y]+1);
                        }
                    }
                }
            }
        }
    }
    if(dp[n][m]==1e18)cout<<"-1\n";
    else cout<<dp[n][m]<<"\n";
    return 0;
}