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

杨利霞

0 C) G$ ]  q! g% q0 {# _2019第十届蓝桥杯B组决赛题解第六题
3 N% d& j# u, j- O8 s2 {题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T
- }2 W  M" n1 }
# `! B* f3 U- }9 ?" h思路:dp+贪心
: t, B" u& a/ D) X4 G% i. r8 d
f[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，
" I$ f. k( _! \9 i! k9 ?. P% g1 o即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配

过程简述如下：
6 [3 [! x( U: ?- @0 OS：  ABCECDFF
T：  BBDEC
1 W! z0 A! [) y" Z  w; c4 F
开始i=1,j=1
! c4 v( \# L8 S* |  z在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中的字母

, Q2 @" T/ ]5 {& k5 v3 ?; F本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码
  i/ T) o2 R5 b+ s6 q4 @( R1 O8 Y还需要把f[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算
  T/ [, Y' j: F
代码:
---------------------
5 R# @1 v& V5 \* I; t作者：nka_kun
来源：CSDN
- ^$ B. f0 v' r& J' M
( p4 O9 {* t8 d& N# {0 D