- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 564681 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174627
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
; H* h* w1 s4 H( W0 m& D; A. G
2019第十届蓝桥杯B组决赛题解第六题* K9 H/ }" u( U5 C3 I. F5 @4 a5 Q$ U
题意:输入一个S串和一个T串,|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T3 m [, A( [" X" m$ D& X
- e2 V4 _/ u! F G4 G思路:dp+贪心$ Q4 n# @' d" k# N4 G
# E K9 s: U7 g; R
f[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数," F: D, T( ?! W3 c
即S中i之前的字母已经包含T中j之前所有的字母,所以分别从i和j位置继续匹配
+ k8 F. _5 W# G, a3 k
/ M5 D! \% I/ Z' m& t9 P过程简述如下:
+ X/ X% P; R h2 K! AS: ABCECDFF9 V9 X6 H! `0 M. Y! L+ Y' l" c
T: BBDEC
" O4 m3 {% c5 M
) w# Y& \6 ^" t9 ?$ v开始i=1,j=1/ {3 O% e" J- y( P
在S开始寻找T[j]即'B',在i=2位置找到,此时我们面临两个选择,要么就让i=2和j=1匹配,要么就修改i=1的'A'为'B',因为既然修改肯定就修改最前面的
: y7 u: S0 Q$ h假如选了前者,接下来就从i=3,j=2继续匹配,假如选了后者,就从i=2,j=2继续匹配,无论怎么选,后面面临的子问题和刚才面临的问题一模一样
7 R ~ l: \0 N' G0 N& H9 i! k/ ]$ I- _对于这个样例,选择后者总共只需要修改2个S中的字母,选择前者总共需要修改3个S中的字母& j4 C' L; x! ~6 a+ t
4 c5 Q1 R5 @" N) P2 H
本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里,预处理见代码9 \0 B7 i' s, x
还需要把f[j]记录清楚,因为有很多重复的子问题我们没有必要重复计算( ~+ o9 H% i: T6 H
2 f' E" Q( @0 E. q, p
代码:7 y; v7 ~8 v$ W2 S
--------------------- 9 M9 B2 w9 i( o2 [) D; A
作者:nka_kun
9 J' M' k! j+ D来源:CSDN
" k1 k3 a1 `) ~# b
8 S: s& z! ]0 J; O4 d' [" }7 y7 X# G
0 O! t- H- n$ P6 Z4 _
|
zan
|