数学建模社区-数学中国

标题: 2019第十届蓝桥杯B组决赛题解第六题 [打印本页]
作者: 杨利霞    时间: 2019-6-28 16:07
标题: 2019第十届蓝桥杯B组决赛题解第六题

* ]9 R) j2 t" f4 \8 m; e2019第十届蓝桥杯B组决赛题解第六题
+ `; E  ~9 f3 w2 n7 C- X& l题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T# j0 I$ c" D) X
+ I5 w4 N- p1 @% s) o
思路:dp+贪心
  R. @/ y  f# p. [5 c3 f! {5 {9 `
: w+ u, f/ }; A3 M3 r8 ?8 Mf[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，
# G  y0 B/ Y. ~" c8 Z7 X% j; z即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配
7 K% T  d6 ~6 q& ?" ~9 Q( M! n4 A9 f/ c
过程简述如下：
* _4 f! ^( p) z* r8 o) S0 E7 e& V+ y* LS：  ABCECDFF
. m: f2 S+ L: I* a! E8 J' ZT：  BBDEC- P" U( e5 G6 i1 `' g5 y7 t  Z
% F  X; ~) `, P- }0 l1 A; |  v1 A
开始i=1,j=1; I! V! Y; r) |2 q0 s8 ^8 u
在S开始寻找T[j]即'B',在i=2位置找到，此时我们面临两个选择，要么就让i=2和j=1匹配，要么就修改i=1的'A'为'B'，因为既然修改肯定就修改最前面的
4 u7 s* [1 i0 T4 L2 q/ _8 N假如选了前者，接下来就从i=3,j=2继续匹配，假如选了后者，就从i=2,j=2继续匹配，无论怎么选，后面面临的子问题和刚才面临的问题一模一样
1 n5 w6 a1 P$ ]' ?对于这个样例，选择后者总共只需要修改2个S中的字母，选择前者总共需要修改3个S中的字母( a0 m2 e) m" y+ A

/ a0 V$ p. `9 V+ X8 `. q本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码! \, t8 w, ]5 N
还需要把f[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算
  y; ?' z8 P. q+ ?3 A; O- \
$ U- f& P$ P1 Y0 ?( Z) D) o3 @# o代码:& N) k, F) T9 D2 @
--------------------- 4 q, b6 Y  b4 X6 W, Z
作者：nka_kun 4 b& w% a5 Y; g* Q% b0 L# ^
来源：CSDN
4 @) T8 }4 I2 I; j9 O0 M" o
( e4 {' ?/ Y% E. G5 Q2 g: x4 k, e. B! P6 v
+ I) P( N( J# m4 j




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5