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

杨利霞

2019第十届蓝桥杯B组决赛题解第六题
" W2 |6 U* @/ L0 [/ Q& ~1 b3 t% N2 q题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T
1 y8 Z( `& n0 a9 `( T) ^5 z
思路:dp+贪心
" t1 Y" S6 q/ C
. ~% k# h. V5 X. K- e# p" Sf[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，
3 h, |! Q- Z2 M% _/ x# B1 y即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配

8 n3 g8 A, Q( E过程简述如下：
S：  ABCECDFF
T：  BBDEC
) _6 l! z$ p, q# l
; b9 N* n" \% k4 H& u开始i=1,j=1
- ]: A0 F/ I; O& w7 J4 k+ q在S开始寻找T[j]即'B',在i=2位置找到，此时我们面临两个选择，要么就让i=2和j=1匹配，要么就修改i=1的'A'为'B'，因为既然修改肯定就修改最前面的
假如选了前者，接下来就从i=3,j=2继续匹配，假如选了后者，就从i=2,j=2继续匹配，无论怎么选，后面面临的子问题和刚才面临的问题一模一样
- o! g: F: h  m0 X对于这个样例，选择后者总共只需要修改2个S中的字母，选择前者总共需要修改3个S中的字母
1 q) z/ T& v: r+ ]# S' k
% }7 F+ |9 Y, f本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码
( \3 t  \) J5 s/ \还需要把f[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算
% Q2 T+ O7 x" C
: J  g9 Y) R$ [$ W7 D' v0 \代码:
# ~2 \( `- C: L* I6 }& e3 g---------------------
作者：nka_kun
6 e$ a7 B  U8 y5 @3 L来源：CSDN
. S! w# K- P' T/ n