QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3043|回复: 0
打印 上一主题 下一主题

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

    5 b) _; C! Y; I# l( q) Z! H2019第十届蓝桥杯B组决赛题解第六题- v, t. @: X+ C- W: Z9 U' b
    题意:输入一个S串和一个T串,|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T. i( P* a5 |1 K/ O2 g. N
    4 E4 A, N' `7 i  J# i; x
    思路:dp+贪心& W* P; |- e9 I3 c2 x

      i# D2 A8 N' x5 Lf[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数,5 f- w, v6 }; M; N0 Z  v6 W
    即S中i之前的字母已经包含T中j之前所有的字母,所以分别从i和j位置继续匹配! L7 ]3 a' d9 g- }# T9 e* t; Z

    ( v9 g: ^( G& `# L! |过程简述如下:/ l! ]$ |, D! b3 ?. q! F! O
    S:  ABCECDFF; s. A7 ^( G' J6 v$ K
    T:  BBDEC
    # J' Z+ e1 }  e: k. N( `8 o, m% F( U: {# l% C3 K
    开始i=1,j=1, |1 ]" T1 E* n5 U6 z% S; j
    在S开始寻找T[j]即'B',在i=2位置找到,此时我们面临两个选择,要么就让i=2和j=1匹配,要么就修改i=1的'A'为'B',因为既然修改肯定就修改最前面的2 `' Q" O8 v# x
    假如选了前者,接下来就从i=3,j=2继续匹配,假如选了后者,就从i=2,j=2继续匹配,无论怎么选,后面面临的子问题和刚才面临的问题一模一样
    / i/ Q/ [8 V+ Y  Z对于这个样例,选择后者总共只需要修改2个S中的字母,选择前者总共需要修改3个S中的字母) h0 i) d* n# |$ N- B" ?
      R) Q# P2 }5 ]9 E- q
    本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里,预处理见代码' E4 g- [( ]1 Y- N. a
    还需要把f[j]记录清楚,因为有很多重复的子问题我们没有必要重复计算0 ]6 t) g. V9 J5 u) T: [* m& I
      S' }$ |; [0 _: _* Y+ o+ F
    代码:
    8 c! y% |9 E; |) n) }& i---------------------
    5 \' w8 O  I" `+ v6 y9 b作者:nka_kun , c8 |! Q" C* h' ]: i" o. ^
    来源:CSDN 1 }7 n0 N  A  ~4 C

      J9 H; ~* q( O/ F: ]) A4 t7 _
    1 T1 A4 A' B) A6 Y1 c' J
    - ^' Q" O1 Z3 K0 U! M& O$ O
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-6-14 03:03 , Processed in 0.525332 second(s), 51 queries .

    回顶部