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

杨利霞

7 O, `: H; f& v3 U2 T2019第十届蓝桥杯B组决赛题解第六题
9 ]( R) l! f' O& N6 b+ A4 u题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T

1 ]5 P& w: L  a- i. L8 W思路:dp+贪心

5 `" q' d" [2 a7 e6 H% Gf[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，
8 K3 \' w$ G# D* X9 O  }1 w% d9 W即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配

$ K% @& B: w6 O+ ?7 J过程简述如下：
S：  ABCECDFF
9 g% R8 I+ M7 rT：  BBDEC
5 z, e' s6 [- o4 l
4 m: X5 W# M( T8 K/ g$ S1 W. M8 R5 q开始i=1,j=1
/ _5 J4 Q7 f. i! _在S开始寻找T[j]即'B',在i=2位置找到，此时我们面临两个选择，要么就让i=2和j=1匹配，要么就修改i=1的'A'为'B'，因为既然修改肯定就修改最前面的
# Q# X! c4 |2 q  U8 p3 I0 b假如选了前者，接下来就从i=3,j=2继续匹配，假如选了后者，就从i=2,j=2继续匹配，无论怎么选，后面面临的子问题和刚才面临的问题一模一样
" p6 `  c# B' c  d对于这个样例，选择后者总共只需要修改2个S中的字母，选择前者总共需要修改3个S中的字母

% C  }, \6 ~' l本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码
还需要把f[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算

代码:
" I3 G2 e. {- m* ~---------------------
作者：nka_kun
; S8 d: A2 D+ \来源：CSDN
/ S0 x: o' {; j% h6 k

/ [1 l0 d7 z2 L; y9 h3 R% k