2019第十届蓝桥杯B组决赛题解第六题

杨利霞

2019第十届蓝桥杯B组决赛题解第六题
9 L; N% g! z3 v) _9 h题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T
* H% A) v4 C3 R7 `  m+ ]" _
* Q: A3 R8 }. |* A2 O, @思路:dp+贪心

2 Q' v  T5 G5 ?f[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，
, D4 X4 I( s, B/ d6 e即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配

过程简述如下：
S：  ABCECDFF
' d+ U7 @( [! h) N0 i, RT：  BBDEC
) k' s: ?$ e% m; H
开始i=1,j=1
- j8 M1 L" v4 X7 G在S开始寻找T[j]即'B',在i=2位置找到，此时我们面临两个选择，要么就让i=2和j=1匹配，要么就修改i=1的'A'为'B'，因为既然修改肯定就修改最前面的
假如选了前者，接下来就从i=3,j=2继续匹配，假如选了后者，就从i=2,j=2继续匹配，无论怎么选，后面面临的子问题和刚才面临的问题一模一样
对于这个样例，选择后者总共只需要修改2个S中的字母，选择前者总共需要修改3个S中的字母
! F) Z3 M, g3 K5 Z0 ]! c
本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码
: W6 Z9 d2 y) s5 K9 g4 G( ~还需要把f[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算

$ b) ?8 a5 v* f7 n6 s7 H5 [' _, K代码:
---------------------
. k% u, p  z. @9 y" I3 z# z% u* Z作者：nka_kun
来源：CSDN

8 Y& B( K0 d; E) F: K% J
7 T" R* h+ Z8 e  C" u# p