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

杨利霞

2019第十届蓝桥杯B组决赛题解第六题
4 R# Z1 e- W" r题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T
: S4 n- t- f6 B* c. r3 Z: a  P" X
思路:dp+贪心
5 g* m% @- E3 x, z4 a* s" [" B
& E" r# O8 E4 H2 n/ Xf[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，
即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配

! Z$ C, a- c0 l# a% c过程简述如下：
* R; w# e- ?  ?0 d9 L; s7 _4 ZS：  ABCECDFF
- t3 Z' K8 K8 {T：  BBDEC
8 M. c7 R' X6 C( J1 p3 I, ]% N- L. H
* |3 w* i& r) Y9 g开始i=1,j=1
在S开始寻找T[j]即'B',在i=2位置找到，此时我们面临两个选择，要么就让i=2和j=1匹配，要么就修改i=1的'A'为'B'，因为既然修改肯定就修改最前面的
/ K6 S; x! t& u6 M7 t6 F假如选了前者，接下来就从i=3,j=2继续匹配，假如选了后者，就从i=2,j=2继续匹配，无论怎么选，后面面临的子问题和刚才面临的问题一模一样
$ s5 P0 ]1 f/ E4 d0 F对于这个样例，选择后者总共只需要修改2个S中的字母，选择前者总共需要修改3个S中的字母
% W2 ^% m& H. z( ~
* R+ E8 u4 \6 x5 y5 Y$ z本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码
2 ~4 o* I1 N4 H7 h3 w还需要把f[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算
" i, \0 ]6 t. L( P' N$ W; L
代码:
+ K: ?  l* k' x- k---------------------
1 C% b+ N  h2 c4 F, A! b作者：nka_kun
来源：CSDN

9 w7 N7 _7 z. F$ d8 g
. u2 R: |" Y# @) B8 o
$ p2 @2 ~! W, }, B