kanpurin https://blog.hatena.ne.jp/kanpurin/ かんプリンの学習記録 https://kanpurin.hatenablog.com/ yukicoder 動的計画法 典型 期待値 競技プログラミング 解説 問題はこちら 問題概要 解説 提出プログラム 感想 問題概要マスのマス目がある．以下の操作のうちつを選び，マスからマスまで移動するときの操作回数の最小値を求めよ． 操作：マスにいるときマスに移動する． 操作：ワープマスにいるときランダムにワープマスに移動する． ワープマスはマスある(がワープマス)．解説 ワープマス以外のマスは操作が決まっているので圧縮します．のケース赤丸がワープマス．矢印が操作回数． 最左のワープマスより左のマスと最右のワープマスより右のマスの操作回数はあとでまとめて足します． を「マスからマスに移動するまでの最小の操作回数の期待値」とすると遷移の式は以下の様になります． こ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkanpurin.hatenablog.com%2Fentry%2F2021%2F04%2F16%2F230404" title="yukicoder No.1478 Simple Sugoroku - かんプリンの学習記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/k/kanpurin/20210416/20210416224351.png Hatena Blog https://hatena.blog 2021-04-16 23:04:04 rich https://kanpurin.hatenablog.com/entry/2021/04/16/230404 1.0 100%