专栏文章

题解：CF49E Common ancestor

hhoko
CF49E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miozrah3
此快照首次捕获于
2025/12/03 03:49
3 个月前
此快照最后确认于
2025/12/03 03:49
3 个月前
查看原文

题目传送门

题目大意

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

思路

注意到 n≤50n\le 50，所以我们考虑区间 dpdp。先预处理出一个 visi,j,kvis_{i,j,k} 表示字符 ii 和字符 jj 可以转换成字符 kk。
我们分别对两个字符串进行区间 dpdp，我们定义 fi,j,zf_{i,j,z} 表示，字符串的 [i,j][i,j] 经过若干次转换后可以变成字符 zz。我们枚举 k∈[i+1,j−1]k\in [i+1,j-1]，如果 fi,k,xf_{i,k,x} 为真，并且 fk+1,j,yf_{k+1,j,y} 为真并且 visx,y,zvis_{x,y,z} 为真，那么 fi,j,zf_{i,j,z} 为真。
假定我们对两个字符串区间 dpdp 完后的数组分别为 fafa 和 fbfb，那么如何统计答案呢。统计答案时我们用动态规划，定义 dpi,jdp_{i,j} 表示处理完第一个字符串的前 ii 位和第二个字符串的前 jj 位后，两个字符串能变成的最短的且相同的字符串长度。我们枚举 x∈[0,i−1]x\in[0,i-1] 和 y∈[0,j−1]y\in[0,j-1] 如果 fax+1,i,zfa_{x+1,i,z} 为真并且 fby+1,j,zfb_{y+1,j,z} 为真，那么 dpi,j=min⁡(dpi,j,dpx,y+1)dp_{i,j}=\min(dp_{i,j},dp_{x,y}+1)。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...