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个字母开头的串所要修改的最少的字母数，
! J6 _; u) \% H& X% _6 C即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配5 z8 z# C, }, l- q3 B; z+ u( X
5 e1 f9 F# `$ Y+ ?: G% ~
过程简述如下：. B% ~5 k9 Z$ I$ u# i6 j" @; t8 W
S：  ABCECDFF
" h" T* o2 t1 Y7 }! P6 e, zT：  BBDEC
+ r1 N3 k8 d2 x# @! c" O: z2 P/ S( F: i, `' h! c  A
开始i=1,j=1* i. @- P& H- X% x# w9 _! |
在S开始寻找T[j]即'B',在i=2位置找到，此时我们面临两个选择，要么就让i=2和j=1匹配，要么就修改i=1的'A'为'B'，因为既然修改肯定就修改最前面的( v3 h  }5 ?* L
假如选了前者，接下来就从i=3,j=2继续匹配，假如选了后者，就从i=2,j=2继续匹配，无论怎么选，后面面临的子问题和刚才面临的问题一模一样
4 l- C, @$ L# v# C8 s对于这个样例，选择后者总共只需要修改2个S中的字母，选择前者总共需要修改3个S中的字母
$ A- }  d4 o  a( c0 q8 t9 P  N' G) _$ V2 i6 a  H
本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码
1 l! P6 u+ r, [3 |还需要把f[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算& w( }4 S: O! {# @8 `9 ]6 O0 d- k! X

% p+ U! {# _. M: P. v代码:5 m# Y8 L3 n( j+ }: Y5 X& B# n
---------------------
% A) p) n) g3 \: @/ n$ ?% k# h. d作者：nka_kun + w- V1 R, F- D% C( y
来源：CSDN ( x+ U% B  L1 `3 i& {! ~
' I0 W# K" l2 ^$ G4 j2 J8 [2 r1 U
0 m. h5 ?0 v$ B

& [% L' y7 Y$ Z( }5 [/ w