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

杨利霞

0 ?2 h9 t( x0 T: O# F/ H7 N2019第十届蓝桥杯B组决赛题解第六题
题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T

思路:dp+贪心

f[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，
即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配

, Z+ ]% M. F; ?" X2 n6 A8 k$ f2 E1 A过程简述如下：
0 z& e+ z$ t# V8 v: NS：  ABCECDFF
T：  BBDEC

* M; ?1 l4 w/ v  L2 ]8 [开始i=1,j=1
2 r& K: \& Q. B. w在S开始寻找T[j]即'B',在i=2位置找到，此时我们面临两个选择，要么就让i=2和j=1匹配，要么就修改i=1的'A'为'B'，因为既然修改肯定就修改最前面的
假如选了前者，接下来就从i=3,j=2继续匹配，假如选了后者，就从i=2,j=2继续匹配，无论怎么选，后面面临的子问题和刚才面临的问题一模一样
7 g2 Z, U0 V* f! N% u7 f对于这个样例，选择后者总共只需要修改2个S中的字母，选择前者总共需要修改3个S中的字母
& P$ [& q4 l# m3 ?5 O8 ]! J+ ?8 V5 M
7 d) p: ~) \* {* S, M; t' k5 R本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码
$ N+ ]- m) f: F! [还需要把f[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算
8 A  M* h' J% H+ W
/ g# T# ?+ H- k7 t代码:
( S0 H9 P6 z$ P5 b8 z1 Z2 d---------------------
作者：nka_kun
来源：CSDN