hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/D 前提知識 動的計画法 考察過程 1. 難しく見えるし、最小値を求めているし、DAGっぽくもあるので、DP方針で考える 2. 「dp[i] := i番目まで到達するための単語の最小個数」がぱっと思いつくDP 3. dp[i]を確定したいが、遷移元はdp[i-1]とi番目の先頭がcであれば、i番目より前のcの1つ前のdp[j] 4. 文字ごとにdp[j]の最小値を持っておけば遷移を高速化できる 5. 解けた 解法 https://onlinejudge.u… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2018%2F09%2F23%2F084202" title="しりとり圧縮 (Shiritori Compression) [Aizu Competitive Programming Camp 2018 Day 3 D] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-09-23 08:42:02 rich https://blog.hamayanhamayan.com/entry/2018/09/23/084202 1.0 100%