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

杨利霞

9 o* Y5 _; {& R% A2019第十届蓝桥杯B组决赛题解第六题
* N7 p' R$ w* R) j) ?2 ~& x$ j题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T

" ?% T) Q. B' G/ X7 Y% C! A+ T思路:dp+贪心
) T8 y# b# ~5 k" _4 u0 p0 x7 O
+ u" ~" S8 X5 ?, B6 O+ Z7 {f[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，
即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配

过程简述如下：
S：  ABCECDFF
T：  BBDEC

5 V: p- Z# P3 R+ x* D开始i=1,j=1
; S( r: K1 `8 ^在S开始寻找T[j]即'B',在i=2位置找到，此时我们面临两个选择，要么就让i=2和j=1匹配，要么就修改i=1的'A'为'B'，因为既然修改肯定就修改最前面的
假如选了前者，接下来就从i=3,j=2继续匹配，假如选了后者，就从i=2,j=2继续匹配，无论怎么选，后面面临的子问题和刚才面临的问题一模一样
. {' ^- N9 z" l8 z# p8 _对于这个样例，选择后者总共只需要修改2个S中的字母，选择前者总共需要修改3个S中的字母
) f6 b' ~: Z  d1 i* Z( c
: u4 x+ H* B- \! y% \1 q本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码
' \" J! _2 m) j* Z9 s! _8 {# @/ n还需要把f[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算
2 X' G8 @9 Z2 D0 q
代码:
1 w8 m9 l& s  k% e---------------------
作者：nka_kun
  i: {+ Y, [( h) @1 x; Z( T+ Q来源：CSDN
& Z" t4 b# y% J2 O2 f
! l) [% [! K0 k0 k

7 Q" j0 H, C( o8 M; u! @  g