https://kanpurin.hatenablog.com/entry/2021/06/23/011004

問題概要

最初紙に ${1}$ 文字書いてある．コピーとペーストを行うことにより，紙に ${N}$ 文字以上書いてあるようにしたい．コピーには ${C}$ ，ペーストには ${V}$ のコストがかかる．最小でいくらのコストがかかるか．

${2\leq N\leq 50000\\ 1\leq C,V\leq 1000}$

解説

連続でコピーする必要はない．「1回のコピーと ${k}$ 回のペースト」を複数回行う． ${i}$ 文字書かれていたときにこの操作を行うとコスト ${C+Vk}$ で ${(k+1)i}$ 文字書かれた状態にできる． ${i}$ 文字書かれているというのをグラフ上の頂点 ${i}$ に，前述の操作を ${i}$ から ${(k+1)i}$ へコスト ${C+Vk}$ の有向辺に対応させる． ${(k+1)i}$ が ${N}$ を超える場合は ${N}$ とする．辺の数は調和級数を用いて ${N\log N}$ になる．ダイクストラ法を用いて頂点 ${1}$ から頂点 ${N}$ までのコストの最小値を求めればよい．計算量は ${O(N\log^2 N)}$ となるが，このグラフはDAGなので単純なDPで解ける．計算量は ${N\log N}$ ．

提出プログラム

https://yukicoder.me/submissions/669107 ダイクストラ

感想

こんな感じでグラフの最短路問題に落とし込むやつ好き