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

杨利霞

/ _; _5 F& p) ~- |3 X$ U+ k2019第十届蓝桥杯B组决赛题解第六题
题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T

$ g8 Q' z# \; X8 S, S! t3 \* X思路:dp+贪心

f[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，
- _' V- i2 B. I/ d# C即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配

0 P8 b( V. C- u. K2 R2 ]* T7 p过程简述如下：
. B* p# s1 ~. Z; O# z* Y; ]+ r, PS：  ABCECDFF
T：  BBDEC
- h5 \& ~' N% U/ W( K
" x- Q8 u) W- _8 g: U开始i=1,j=1
在S开始寻找T[j]即'B',在i=2位置找到，此时我们面临两个选择，要么就让i=2和j=1匹配，要么就修改i=1的'A'为'B'，因为既然修改肯定就修改最前面的
$ w( L& C9 j$ a* D" b. P3 r. h假如选了前者，接下来就从i=3,j=2继续匹配，假如选了后者，就从i=2,j=2继续匹配，无论怎么选，后面面临的子问题和刚才面临的问题一模一样
对于这个样例，选择后者总共只需要修改2个S中的字母，选择前者总共需要修改3个S中的字母

  J5 G$ I! S3 L3 W, X- K6 F, }本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码
) |# u: c4 l" o; Y* k& `' p; t还需要把f[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算
6 }/ i, z. j& e$ ?. h# H5 {
! o% T0 N$ M5 [8 A( G5 w; q代码:
  l; j, J) `' r; u0 v$ f( W6 P---------------------
作者：nka_kun
) \, q) w) E; V' _. L$ d/ f来源：CSDN
* a6 i" V) e' j5 ^
+ N9 o1 h  D! \/ q, l9 F

3 I" P' h% x! T( @