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

杨利霞

2019第十届蓝桥杯B组决赛题解第六题
" @  M) f- k0 F$ {# n, S题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T

思路:dp+贪心

. g9 J5 u% j8 z1 Y% Q( \f[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，
3 A+ L" }1 i1 d# {/ h4 i; m' c: C0 q即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配
2 \" l0 O( B& T/ ], m* q$ c. S
过程简述如下：
S：  ABCECDFF
+ [; ?; e( T, u4 _2 X! m" FT：  BBDEC
1 g! q. I) O, h, g
; O8 [" x  e/ _3 ~& p* ^开始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中的字母
& ?; D. C0 w) G, |1 X$ @
. E! M3 o& _+ W8 ~/ f本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码
* P) h8 i/ u4 Q' j- t还需要把f[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算
: }' T9 Y, v" x
* d) Y) I# m$ F) M6 V代码:
4 t, s& H  k' e---------------------
7 X+ d# r) j6 z' M9 m5 O作者：nka_kun
2 H$ f% e& N4 w8 D0 H6 p0 @& U6 M+ T来源：CSDN
6 S, {/ q1 y4 Y# A9 U
/ d2 `2 A2 a- k, f/ Q8 |8 o
7 x- t, _/ i! r2 o0 `$ ?. E