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

杨利霞

/ d1 X$ [4 I& O/ D; ^- F2019第十届蓝桥杯B组决赛题解第六题
$ W* m% M. f+ Z. A! w- m题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T
4 h; n, C+ t/ G* l
7 z' q1 K: r9 F8 X7 f思路:dp+贪心
2 s- a3 H, M. R# \6 o
f[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，
6 D- Z+ N6 D0 M. Y: L4 ~6 ?- i即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配

过程简述如下：
6 U9 Z. Y/ G: k7 VS：  ABCECDFF
& s0 y) l, S( w# D2 t* }" Z0 b  W; yT：  BBDEC
( W8 M0 m7 D/ }8 k
开始i=1,j=1
在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中的字母

本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码
+ A2 v& F8 ], U  C- m# H还需要把f[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算
9 G3 f2 J. E# _  R
, m/ C. ~# |4 F) w! T8 ~代码:
) [& }$ I7 h/ b) L4 x---------------------
/ b% K3 R' |) {1 c* @& i作者：nka_kun
来源：CSDN



# D7 L6 M# ^' Q+ @* R: F6 J