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

[复制链接]

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2019-6-28 16:07 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

2019第十届蓝桥杯B组决赛题解第六题
题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T

思路:dp+贪心

f[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，, d# E! u& j0 q7 T/ s% d
即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配# V+ e, {+ o7 L. J0 [# f
1 I( ]7 r; t% K; @
过程简述如下：! A1 J5 h4 l) C4 U& h4 n
S：  ABCECDFF# @6 n$ ?9 |- z9 x
T：  BBDEC, ^1 B' C# h/ z1 T. @# z

$ m7 ]& o% c5 I开始i=1,j=1/ f5 X9 l6 Q1 X% L, o9 t* L8 h
在S开始寻找T[j]即'B',在i=2位置找到，此时我们面临两个选择，要么就让i=2和j=1匹配，要么就修改i=1的'A'为'B'，因为既然修改肯定就修改最前面的4 ^4 s  z% }1 N) l* Z5 y8 M' ]
假如选了前者，接下来就从i=3,j=2继续匹配，假如选了后者，就从i=2,j=2继续匹配，无论怎么选，后面面临的子问题和刚才面临的问题一模一样
. Y/ W% L; [3 N' m4 h对于这个样例，选择后者总共只需要修改2个S中的字母，选择前者总共需要修改3个S中的字母
& p- R! A: ^. R' z( s$ P( K& h8 Q* f; m/ k& ~5 [
本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码1 D4 e3 H" d+ m! D
还需要把f[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算4 f  o  B5 y  ~+ U* T4 O8 v0 b( j
# g" E1 t% e1 Q. j+ N$ A
代码:$ h" C; d# R+ N$ s3 C0 C
---------------------
# n% g) r/ H5 E: |  z" Y  u) G作者：nka_kun
0 g* t6 }; m) c2 Y4 y' m, e来源：CSDN 2 P- A( h1 Q" p9 h  E

7 T! J5 Q; p: a/ I, c6 z0 I0 E* S+ |" R' |5 C7 t. x& ~8 O) |
3 h6 V7 {% B/ n* h8 ]8 u7 l* c: m