この問題を自力 AC しました。バチャでは前の E に詰まって F まで見れませんでした、E に詰まったら F を見よう！の典型ができませんでした。
問題概要
文字列 と長さ
の文字列
、整数
が与えられる。文字列
の任意の要素を任意の文字に置き換える操作を
回まで行うことができる。文字列
の長さ
の部分列のうち、
と一致するものの数を最大化したときの値を答えよ。
考えたこと
前と後ろから何個変更するかを決め打ちしたらできませんか？
→う〜ん、厳しい。 を
に変えたいときの判定とかどうしたら良いかわからない。
とりあえず動的計画法で何回変えたか、 の数、
の数を保持しておけば
ではいけそう。遷移を考えると
の数は要らなさそう。
