CF67C Sequence of Balls(字符串dp&思维) 题解

发布于 2021-08-24  84 次阅读


前面的话

好题。但是找遍全网没有感觉特别深入的题解,对于我发出的一些疑问也很难解答。这里发布详细的题解以及一些跟同学讨论过后 的结论以及思绪,希望能给你帮助,更希望你能给我点个赞

题目大意

你有四种操作:

  1. 插入任意一个字符,花费 $t_i$ 元。
  2. 删除任意一个位置的字符,花费 $t_d$ 元。
  3. 替换任意一个字符为其他字符,花费 $t_r$ 元。
  4. 交换任意相邻两个位置的字符,花费 $t_e$ 元。

给定两个字符串 $a,b$。对 $a$ 进行任意次以上四种操作,求变成 $b$ 的最小花费。

$|a|,|b| \le 4 \times 10^3$,$1 \le t_i,t_d,t_r,t_e \le 100$。

解题思路

dp 的思路是显然的,状态也不难想,与类似的题目相同,都是设 $dp_{i,j}$ 为 $a$ 串的前 $i$ 个字符,$b$ 串的前 $j$ 个字符匹配上的最小花费。

那么我们分别考虑四种操作。

对于插入操作,我们先给出方程:
$$
dp_{i,j}=\min { dp_{i,j} , dp_{i,j-1}+t_i }
$$

pic1.png

如上图,我们进行的操作,是把 $b_j$ 这个字符插入到 $i$ 的后面。也就是说,原来匹配的字符有 $j-1$ 个,现在有 $j$ 个了。

那么为什么不是从 $dp_{i-1,j-1}$ 转移过来呢?我们考虑本来 $a$ 的前 $i$ 位就已经和 $b$ 的前 $j-1$ 位匹配的情况下,我们现在用的是加的这位去和 $b$ 的第 $j$ 位匹配。

那为什么不是转移去 $dp_{i+1,j}$ 呢?因为我们插入和删除字符,显然不能真的去修改原串。我们 $dp$ 数组里的 $i$ 和 $j$ 都是指原串中的位置,是不受插入删除的影响的。换言之,这个加进来的字符,不可能对答案造成贡献我们在后面处理的时候是不考虑的

那为什么可以不考虑呢?这个我们最后说,和交换操作有关。

减法同理,直接给出方程吧:
$$
dp_{i,j}=\min{dp_{i,j},dp_{i-1,j}+t_d}
$$
也即,$a$ 的前 $i-1$ 位已经与 $b$ 的前 $j$ 位匹配了,我们现在直接删去 $a$ 的第 $i$ 位,维持这个匹配状态。这个减去的字符,也不可能对答案造成贡献,我们不考虑

替换也很简单,不过这里有一种特殊情况:当 $a_i$等于 $b_j$ 时,我们其实是不用替换的,我们视作替换的代价为 $0$。方程就是这个:
$$
dp_{i,j}=
\begin{cases}
\min{dp_{i,j},dp_{i-1,j-1}} \quad , \quad a_i=b_j \\
\min{dp_{i,j},dp_{i-1,j-1}+t_r} \quad , \quad a_i \ne b_j
\end{cases}
$$
最后就是交换了。假设当前处理到 $dp_{i,j}$,我们只需要找出位置在 $i$ 左边的 $a_{p_1}$ 以及位置在 $j$ 左边的 $b_{p_2}$,满足 $a_{p_1}=b_j$,且 $b_{p_2}=a_i$,那么我们如果能够交换 $a_{p_1}$ 和 $a_i$(只能对 $a$ 串进行操作),之后就能把这一位匹配上。

显然,$a_{p_1}$,$b_{p_2}$ 是不一定与我们正在操作的这一位相邻的,无法通过简单的一次交换就完成操作。那这个操作的花费是多少呢?

我们考虑两种交换 $a_i$ 与 $a_{p_1}$ 的方法:要么一直对相邻两位进行交换,直到把 $a_i$ 换到 $a_{p_1}$ 处,之后再通过交换把 $a_{p_1}$ 换到 $a_i$ 处。要么先删除 $a_1$ 与 $a_{p_1}$ 之间的障碍,再交换此时已经相邻的两位,再把中间的部分填充回去。至于两种方法的缝合体,显然没有单纯的两种方法优秀。

哪种方法更加优秀?我们发现,题目中给了一条奇怪的条件:$2 \times t_e>t_i+t_d$。什么意思呢?

我们考虑第一种方法的操作次数:

pic2.png

如上图,显然对于一半情形次数为 $2\times (i-p_1)-1$ 次,花费为 $(2 \times (i-p_1)-1) \times t_e$。

考虑第二种方法,显然需要 $i-p_1-1$ 次删除和插入,以及 $1$ 次交换,花费为 $(i-p_1-1)\times (t_i+t_d) + t_e$。

前者减一下后者(看起来很麻烦,实际上是小学数学):
$$
\begin{aligned}
&\quad (2 \times (i-p_1)-1) \times t_e -(i-p_1-1)\times (t_i+t_d) - t_e \\
&=2\times t_e \times (i-p_1-1) - (t_i+t_d) \times (i-p_1-1) \\
&=(2 \times t_e - t_i-t_d) \times (i-p_1-1) \\
&\qquad \qquad \qquad \qquad \because 2 \times t_e > t_i+t_d \\
&\qquad \qquad \qquad \qquad \therefore 原式>0
\end{aligned}
$$
也即,后面的方法一定比前面的方法优。

所以就有了我们的第四个公式:

注意这里是从 $dp_{a_{p_1}-1,a_{p_2}-1}$ 转移过来,因为实际上第二种操作的过程一次性满足了一整段 $[p_1,i]$ 的需求

那么就有了我们的转移方程:
$$
dp_{i,j}=\min{ dp_{i,j} ,dp_{p_1-1,p_2-1} +(i-p_1-1) \times (t_i+t_d) + t_e}
$$
至于 $p_1$ 和 $p_2$,我们直接从前往后用 $O(|S| \times n)$ 的时间复杂度扫过两个串,用类似于序列自动机的东西统计一下即可,好想好写。$|S|$ 指字符集大小,本题中为 $26$。

现在我们再回头去看为什么加入和删除操作不需要考虑加进来的和删出去的那一位:

首先,显然加入和删除只可能对交换操作产生影响。也就是,插入的一位在交换操作中造成了额外的删除负担,或者被删去的一位在交换操作中被错误地多计算了一遍。但是实际上这两种情况不可能发生,因为我们的交换是从 $dp_{p_1-1,p_2-1}$ 转移过来的,跳过了中间的部分,所以不会产生影响。

思路到这里就结束了,写一个 $O(n^2)$ 的 $dp$ 即可。注意实现细节中有一些要注意的部分,比如注意处理 $dp_{0,i}$ 以及 $dp_{i,0}$ 部分的转移,其他的问题就不大了。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=4005;

int n,m,c1,c2,c3,c4;
int dp[N][N],pos1[N][26],pos2[N][26];
char s[N],t[N];

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*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline void Prepare(){
    for (int i=1;i<=n+1;++i){
        for (int j=0;j<26;++j)
            pos1[i][j]=pos1[i-1][j];
        if (i>1) pos1[i][s[i-1]-'a']=i-1;
    }
    for (int i=1;i<=m+1;++i){
        for (int j=0;j<26;++j)
            pos2[i][j]=pos2[i-1][j];
        if (i>1) pos2[i][t[i-1]-'a']=i-1;
    }
}

int main(){
    //freopen("CF67C.in","r",stdin);
    //freopen("CF67C.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>c1>>c2>>c3>>c4;
    cin>>s+1; cin>>t+1;
    n=strlen(s+1),m=strlen(t+1);
    Prepare();
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for (int i=0;i<=n;++i)
        for (int j=0;j<=m;++j){
            if (j>0) dp[i][j]=min(dp[i][j],dp[i][j-1]+c1);
            if (i>0) dp[i][j]=min(dp[i][j],dp[i-1][j]+c2);
            if ((i>0) && (j>0)){
                if (s[i]==t[j]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
                else dp[i][j]=min(dp[i][j],dp[i-1][j-1]+c3);
                int p1=pos1[i][t[j]-'a'],p2=pos2[j][s[i]-'a'];
                if ((p1>=1) && (p2>=1)) dp[i][j]=min(dp[i][j],dp[p1-1][p2-1]+(i-p1-1)*c2+(j-p2-1)*c1+c4);
            }
        }
    printf("%d\n",dp[n][m]);
    return 0;
}

我们无法选择过去,但我们可以改变未来。