cf div1 692-B
問題
からなる文字列
が与えられる.
中の
を全て
に書き換えて得られる文字列に対して、(連続とは限らない)部分列
が現れたらコスト
、
が現れたらコスト
がかかる.コストの最小値を求めよ.
解法
として一般性を失わない(そうでない場合、
をswap,
中の
をそれぞれ
に置き換えればよい).
中の全ての
を書き換えた後の文字列を
とすると、最適な
であって
を満たす整数組
は存在しないようなものが存在する.これはこのような組が存在するとして、
と
をswapしてもコストが増加しないことが容易にわかるため.
この考察での置き換え方は高々
通りに絞られたため、差分を管理していけば最小値が求まる.
考察
と
どっちを減らしたいかわからないので一つにそろえたくなる.
なんとなくの順の置き換え方は良くなさそうとわかる.
