! q7 r/ G1 J0 O0 B2 x. d; g 2019第十届蓝桥杯B组决赛题解第六题 4 _' c8 |$ ~6 i5 o. h+ m# l题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T9 P5 L& O( U! N% [5 p
) Y' ?) D9 I9 a8 u0 f$ v
思路:dp+贪心 5 t3 O% ?, C' E" i: j 9 s Y3 y1 c- B/ G6 {- |f[j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，& X a- u8 [: I- p$ I. r
即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配: D ]% H. D* ~) f# R
6 w9 }( k6 F# k5 p! Y, m ?过程简述如下：% f: w% h7 B& ~0 i, N$ v
S： ABCECDFF : j* q. r" @6 h) {T： BBDEC * a! H A+ Q7 `' F8 _6 a, z7 o 8 }3 e4 @, `% F. H开始i=1,j=1) S, d# |8 R: N" d
在S开始寻找T[j]即'B',在i=2位置找到，此时我们面临两个选择，要么就让i=2和j=1匹配，要么就修改i=1的'A'为'B'，因为既然修改肯定就修改最前面的) g3 l) X6 e. `/ }1 l5 p
假如选了前者，接下来就从i=3,j=2继续匹配，假如选了后者，就从i=2,j=2继续匹配，无论怎么选，后面面临的子问题和刚才面临的问题一模一样6 M D9 [/ f( e/ {" q! f, d& M, E
对于这个样例，选择后者总共只需要修改2个S中的字母，选择前者总共需要修改3个S中的字母 . r+ j( V1 i5 g1 |) n ( V. ~6 w- j, G/ g3 }本题我们需要预处理使得我们可以O(1)的查询到1位置后面最近的'B'在哪里，预处理见代码 & n1 `$ T6 }" R. J; R/ P还需要把f[j]记录清楚，因为有很多重复的子问题我们没有必要重复计算: R5 V5 U* m6 |
+ N8 s4 I. Q2 J代码:4 M. v D; m1 C' S# D
--------------------- - T- T+ @% _8 h" R0 |作者：nka_kun , h# u8 v9 F* F# n
来源：CSDN . d. b" L0 o3 T6 f 1 I& ?0 @3 Z! }! `0 K& j, e1 Y- i% r. A6 B x # _! P# s. x& C5 c3 Z , S ]% o: O9 B, O/ M9 L) t
IP卡
狗仔卡
发表于 2019-6-28 16:07
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
