数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第六题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 16:07
标题:
2019第十届蓝桥杯B组决赛题解第六题
* [- b6 S% H! j k( o+ o1 W) I
2019第十届蓝桥杯B组决赛题解第六题
% m3 Z7 V/ Q# |" V
题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T
; c' G( V% S: Y# E0 U
9 M5 Y, B4 u9 B9 A( A
思路:dp+贪心
7 d' Z( } l9 c( H, e. v W$ m
' V! A; ~" t1 P# R
f
[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，
" l1 ?+ O! |2 u9 \
即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配
( a g& [0 Y8 N2 y6 L- \% }% K0 K. Z
* o5 m2 w+ ?0 B
过程简述如下：
+ F3 ?: J2 I9 t
S： ABCECDFF
/ @& V% p; D. j+ x5 s$ t4 [$ r+ T
T： BBDEC
3 V( N( C- c( W
( N$ @$ L( N+ X! A. B& Q" n
开始i=1,j=1
) v) M) N; w- M
在S
开始寻找T[j]即'B',在i=2位置找到，此时我们面临两个选择，要么就让i=2和j=1匹配，要么就修改i=1的'A'为'B'，因为既然修改肯定就修改最前面的
. V( _5 g7 d$ O& H. O" i q
假如选了前者，接下来就从i=3,j=2继续匹配，假如选了后者，就从i=2,j=2继续匹配，无论怎么选，后面面临的子问题和刚才面临的问题一模一样
( x, R/ `' D; e; i% W. g$ z
对于这个样例，选择后者总共只需要修改2个S中的字母，选择前者总共需要修改3个S中的字母
+ |7 `/ m7 g, j' E6 d' |( e. y
* v& ~. J9 \- }& E) q; w
本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码
" L8 d% `# c' a+ S
还需要把f
[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算
: ~. L: j# R ~# G8 s$ q. v5 \. p
+ l* t |/ P: H4 q( L5 F* a/ X
代码:
+ S3 b0 m: Z: h- O
---------------------
/ m) N g# s$ x
作者：nka_kun
& i0 ?0 [. ?1 w7 l! s/ j
来源：CSDN
/ o0 m% _0 t' t+ k D
4 b) t. p, c, O' L! ^: d
( A d( j* t4 y7 @) c- Q
) Q1 _6 C r/ Q" W) H/ T
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5