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

杨利霞

) d! m2 A) s7 ^5 H2019第十届蓝桥杯B组决赛题解第六题
6 l" [- F0 c$ o+ z题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T
; Y. b3 w  Z3 p( {- N  Q! g3 N# E
思路:dp+贪心
5 F- d% I/ P1 d
f[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，
7 h/ z) G0 u" j+ b9 P$ ~, \5 E即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配
, K6 J$ T+ D* H/ e, o
  k, t) A! k& ~过程简述如下：
. y  {+ Y' {- f+ j+ AS：  ABCECDFF
6 D7 J5 ]8 F7 x( G/ oT：  BBDEC
& m4 Y7 d+ B, S3 o; z' v
开始i=1,j=1
& R( m* O. p, S# w, d在S开始寻找T[j]即'B',在i=2位置找到，此时我们面临两个选择，要么就让i=2和j=1匹配，要么就修改i=1的'A'为'B'，因为既然修改肯定就修改最前面的
" c  M$ z: h$ r3 i# d4 j+ n假如选了前者，接下来就从i=3,j=2继续匹配，假如选了后者，就从i=2,j=2继续匹配，无论怎么选，后面面临的子问题和刚才面临的问题一模一样
对于这个样例，选择后者总共只需要修改2个S中的字母，选择前者总共需要修改3个S中的字母

本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码
还需要把f[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算
3 }' l: O0 p9 P; n, y/ f: g% l
代码:
---------------------
作者：nka_kun
0 n) \  N* e; D* @来源：CSDN
! n! C, m  d; C2 F: i( G' J4 Z; M

% f% Q9 y5 B' U