数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第六题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 16:07
标题:
2019第十届蓝桥杯B组决赛题解第六题
" q0 `* A8 _3 O, @1 V, Q
2019第十届蓝桥杯B组决赛题解第六题
$ e, ~ ?, w0 l8 l$ P/ {& P
题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T
8 S- Z9 f2 s8 q- K5 v, T0 _
8 D: S7 Q, V- [- f/ U( q. \( O
思路:dp+贪心
& V* q, j: l8 p
1 n: V( {: [% v5 t9 V+ ?# P4 @
f
[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，
/ A+ Z$ R5 M% p% Q$ C/ {
即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配
8 q( s" Q/ p# |' t) t* R& \5 x U! w
+ ~0 j+ Z0 v" Z
过程简述如下：
) h& w. K/ p$ [% p. S% Q8 e' n6 U
S： ABCECDFF
3 B4 W$ s- X k, T' G" X
T： BBDEC
( u) K- t! q1 g- n6 q1 J
( o. x8 N" o3 O- a9 a8 `4 N8 z
开始i=1,j=1
. U0 } n9 p K/ v2 o
在S
开始寻找T[j]即'B',在i=2位置找到，此时我们面临两个选择，要么就让i=2和j=1匹配，要么就修改i=1的'A'为'B'，因为既然修改肯定就修改最前面的
; B8 T8 c& V e9 F. }8 b
假如选了前者，接下来就从i=3,j=2继续匹配，假如选了后者，就从i=2,j=2继续匹配，无论怎么选，后面面临的子问题和刚才面临的问题一模一样
; |$ g6 z2 I" F1 ]8 |# m
对于这个样例，选择后者总共只需要修改2个S中的字母，选择前者总共需要修改3个S中的字母
4 f3 y& K- S9 m, ?! ~
: |( k. _' a. j; d
本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码
1 \& s2 R( o$ e: @& ?; Q
还需要把f
[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算
* I/ V4 V# ^! z2 B- M' @
o6 S) d* a! y3 F1 |
代码:
' t4 ~; E h5 M! }8 P
---------------------
5 P9 R9 c* y1 h4 c& ?$ }
作者：nka_kun
8 E' o; P: L! r) u
来源：CSDN
- n5 p4 p6 }0 j& L* H3 b, X5 H& q
7 `* N6 i1 m4 V, y
8 ^3 O+ Z% z9 W
7 A4 [% r( c# A: U6 `# g, ~/ g7 M
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5