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
IP卡
狗仔卡
发表于 2019-6-28 16:07
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
