题解abc261G

· · 题解

好难的区间DP。

首先发现一个性质，由于所有的 C_i 长度都是1，所以在最后的答案里，我们的终串 T 的每一段都会代表 S 的单个字符。

对于这种两串匹配的问题我们有一个经典的 dp 模型：

$dp_{i,j}=\min(dp_{i-1,k}+f_{k+1,j,S_i})

其中 f_{l,r,c} 表示 T 串的 [l,r] 被我还原为单个字符 c 的最小代价。

让我们想想 f_{l,r,c} 怎么转移。首先有如果 |A_i|=1。那么 f_{l,r,c}=\min(f_{l,r,c},f_{l,r,A_i}+1)

更进一步的，我们可以对所有 |A_i|=1 的字符串对，给 A_i 到 C_i 连一条有向边，我们可以用 floyd 处理出来 dis_{i,j} 表示字符 i 只通过这种转换到字符 j 的最短路。这里就不写 floyd 的转移了。

所以， f 数组的第一种转移就是：

f_{l,r,c}=\min(f_{l,r,t}+dis_{t,c})

考虑第二种转移，我们区间 [l,r] 可能先合并成了一个字符串，然后这个字符串通过我的操作变成了一个单字符。

所以， f 的第二种转移是：

f_{l,r,C_i}=\min(1+g_{l,r,i})

其中 g_{l,r,i} 表示我的终串 T[l.......r] 被我还原成 A_i 的最小代价。

现在 f 的转移已经没问题了，但是我们发现 g 很难转移，所以我们给 g 再加一维。g_{l,r,i,j} 表示 T[l,r] 被我转化为 A_i[1,j] 的最小代价。那么转移式就很好写了：

g_{l,r,i,j}=\min(g_{l,k,i,j-1}+f_{k+1,r,A_{i,j}})

初始状态 g_{l,r,i,1}=f_{l,r,a_{i,1}}

乍一看没有什么问题，但是, f 和 g 之间的转移有环啊！！先别急，我们把所有转移写在一起观察一下。

1.f_{l,r,c}=\min(1+g_{l,r,i,|A_i|})

2.f_{l,r,c}=\min(f_{l,r,t}+dis_{t,c})

3.g_{l,r,i,j}=\min(g_{l,k,i,j-1}+f_{k+1,r,A_{i,j}})

4.g_{l,r,i,1}=f_{l,r,A_{i,1}}

首先3号转移肯定第一个做，因为它依赖的区间更小，一定被更新过了。这里我们可以钦定 T[l,r] 变成单个字符的方式是：我们先由长度大于等于2的字符串转移来，然后通过 dis 数组扩展到所有位置。而且我们发现通过第3种方式转移的 g_{l,r,i,j} 中的 j 是大于等于2的。所以我们接着做转移1,然后做转移2，最后做转移4。还有，转移2是有环的，所以得用类似 bellmanford 的方式转移。

这里说不太清楚，可以自己意会一下，不懂可以私信我。

#include<bits/stdc++.h>
#define ll long long
#define pc putchar
#define mk make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
inline void write(int x){
    if(x==0){pc('0');return ;}
    if(x<0)pc('-'),x=-x;
    char nnu[25];int top=0;
    while(x){nnu[++top]=x%10+'0';x/=10;}
    for(int i=top;i;i--) pc(nnu[i]);
    return ;
}
string S,T;
int n,m;
int k;
char C[55];
string A[55];
int g[55][55][55][55];
int f[55][55][30];
int dis[30][30];
int dp[55][55];
signed main(){
    cin>>S>>T;
    n=S.size(),m=T.size();
    S='-'+S;T='-'+T;
    k=read();
    memset(g,0x3f,sizeof(g));
    memset(f,0x3f,sizeof(f));
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=k;i++) cin>>C[i]>>A[i];
    for(int i=1;i<=k;i++){
        A[i]='-'+A[i];
        if((signed)A[i].size()==2){
            dis[A[i][1]-'a'][C[i]-'a']=1;
        }
    }
    for(int k=0;k<=25;k++) for(int i=0;i<26;i++) for(int j=0;j<26;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    for(int i=1;i<=m;i++) f[i][i][T[i]-'a']=0;
    for(int i=1;i<=m;i++) for(int j=1;j<=k;j++) g[i][i][j][1]=f[i][i][A[i][1]-'a'];
    for(int len=1;len<=m;len++){
        for(int l=1;l+len-1<=m;l++){
            int r=l+len-1;
            for(int i=1;i<=k;i++){
                for(int j=1;j<(signed)A[i].size();j++){
                    for(int k=l;k<r;k++){
                        g[l][r][i][j]=min(g[l][r][i][j],g[l][k][i][j-1]+f[k+1][r][A[i][j]-'a']);
                    }
                }
            }
            for(int i=1;i<=k;i++) for(int c=0;c<=25;c++) if(C[i]-'a'==c&&A[i].size()>=3) f[l][r][c]=min(f[l][r][c],g[l][r][i][(signed)A[i].size()-1]+1);
            for(int tim=0;tim<=25;tim++){
                for(int c=0;c<=25;c++){
                    for(int t=0;t<=25;t++){
                        f[l][r][c]=min(f[l][r][t]+dis[t][c],f[l][r][c]);
                    }
                }
            }
            for(int i=1;i<=k;i++) g[l][r][i][1]=f[l][r][A[i][1]-'a'];
        }
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=0;k<j;k++){
                dp[i][j]=min(dp[i-1][k]+f[k+1][j][S[i]-'a'],dp[i][j]);
            }
        }
    }
    if(dp[n][m]>=1e9)cout<<-1<<endl;
    else cout<<dp[n][m]<<endl;
    return 0;
}