JOI2009 春合宿 - stamps

• 問題
• AC

とりあえず最短作業時間は単純なDPで求まりそう。$\operatorname{dp}[x][y] := S$を左から$x$文字作り済みで、次に使える文字がOである（$y=0$）あるいはIである（$y=1$）場合の最小操作数、として$\operatorname{dp}[N][0]$が求める値である。使える文字と次に作りたい文字が一致していればコスト0で次に遷移できるし、一致していなければ文字を変更または挿入してコスト1で遷移できる。

また、元のIOI文字列をできるだけ短くするためには挿入の回数を最大化すればよくて、これも同様のDPができるが、最短作業時間のほうが優先なので上のDPと同時にやる必要がある。

形式的には、1つのDPと捉えて、DP配列に入っている値を$(最短作業時間, 挿入回数)$として辞書式の大小関係を与えると考えると、わかりやすいかもしれない。