問題はこちら
問題概要
最初紙に
文字書いてある.コピーとペーストを行うことにより,紙に
文字以上書いてあるようにしたい.コピーには
,ペーストには
のコストがかかる.最小でいくらのコストがかかるか.
解説
連続でコピーする必要はない.「1回のコピーと
回のペースト」を複数回行う.
文字書かれていたときにこの操作を行うとコスト
で
文字書かれた状態にできる.
文字書かれているというのをグラフ上の頂点
に,前述の操作を
から
へコスト
の有向辺に対応させる.
が
を超える場合は
とする.辺の数は調和
級数を用いて
になる.
ダイクストラ法を用いて頂点
から頂点
までのコストの最小値を求めればよい.計算量は
となるが,このグラフはDAGなので単純なDPで解ける.計算量は
.
提出プログラム
https://yukicoder.me/submissions/669107 ダイクストラ感想
こんな感じでグラフの最短路問題に落とし込むやつ好き