Educational Codeforces Round 16 - E. Generate a String
なんか適当なdpをやってもACは出たんですが、正当性が見抜けないのでそうじゃない方の解説で。
解説
dp[i] := i文字作るときの最小コスト
としましょう。
パターンとしては、1文字追加、倍にする、削除、が考えられるが、1文字追加した後に1文字削除は明らかに無駄である。
よって、文字削除は倍にした後の直後だと分かる。
このことから、倍にしたときのコストを、スライド最小値ぽく、deque内を(indexの距離を考慮した)単調増加のようにすれば、全体でで解けました。
提出コード
まとめ
適当にやったdpの正当性が全くわからない…(嘘かもしれない)
dijkstraを落とすための制約だというのは分かる。
