数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第六题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 16:07
标题:
2019第十届蓝桥杯B组决赛题解第六题
; b8 ?( H8 e7 A+ n
2019第十届蓝桥杯B组决赛题解第六题
3 Z3 W8 J+ C" w5 g; S8 [" `1 \
题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T
3 p9 i6 g, [, y' `, a
. R6 n2 p% H( E! E1 Z4 Z0 w, I4 G
思路:dp+贪心
+ N. |) P" `9 O: y* w1 L
+ R# l8 h7 O4 u* C4 b, z
f
[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，
" m: x9 P* Z/ L+ [: l1 N7 Z# V3 K
即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配
" }& U6 p5 M: l: {5 r4 p
|3 J# } H* w& N5 ?' Q
过程简述如下：
7 L5 W5 |" D3 j& Q; d. H
S： ABCECDFF
! D+ z3 ?, z7 Z7 v6 j
T： BBDEC
0 p+ v$ [0 |% [1 s, @3 C
2 p4 {. [% ~* W1 q
开始i=1,j=1
# \6 F! P, I9 ]
在S
开始寻找T[j]即'B',在i=2位置找到，此时我们面临两个选择，要么就让i=2和j=1匹配，要么就修改i=1的'A'为'B'，因为既然修改肯定就修改最前面的
0 `# [2 `( l7 G0 s' N# j
假如选了前者，接下来就从i=3,j=2继续匹配，假如选了后者，就从i=2,j=2继续匹配，无论怎么选，后面面临的子问题和刚才面临的问题一模一样
$ l# r' _7 R* x* z" M; A
对于这个样例，选择后者总共只需要修改2个S中的字母，选择前者总共需要修改3个S中的字母
: d4 p; w. o$ w- m! [) c. K0 j. o
- Z7 u% a# Q( k- K% ~0 F
本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码
{3 p! c: x. g! d* ]& m( ~# s$ h
还需要把f
[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算
' t9 `4 B+ f1 @1 |: D! m
" j- X4 Z4 a$ O
代码:
0 d( B" N7 J9 n# W
---------------------
1 m- V" N5 q0 A5 | W+ q3 P5 x
作者：nka_kun
; O4 C- J3 _/ Y: f9 x& l3 m+ n
来源：CSDN
9 y3 a s& C! S& T" i, h2 t$ V
+ j! d* G/ y5 k4 K9 H/ c
1 b. ~2 @: ]( h' r: s
) Z( s C- p9 u: n5 c8 q
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5