mmxsrup https://blog.hatena.ne.jp/mmxsrup/ srupのメモ帳 https://mmxsrup.hatenablog.com/ yukicoder 区間dp dp 問題 問題概要 i番目の木はA[i]の実が実る. 時刻1で隣の木にいどうすることができる. 移動しなくてもよい. このような条件ですべての実を回収するのにかかる時間の最小値を求める. 解法 区間dpで解けるみたい. 今回の問題を考えるにあたって重要な考察は, i番目の実を回収する時刻はその実を最後に通過するときでよいということである. 実が消えるわけでないので, 最後に訪問するときに回収すれば十分である. このように実を回収するのを最後の訪問時と決めて考えると, 実を回収してない区間が, 連続間であらわすことができるようになる. dp[l][r][isright] := isright = 0… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmmxsrup.hatenablog.com%2Fentry%2F2017%2F02%2F15%2F134755" title="yukicoder No.484 収穫 - srupのメモ帳" 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/m/mmxsrup/20170215/20170215134532.jpg Hatena Blog https://hatena.blog 2017-02-15 13:47:55 rich https://mmxsrup.hatenablog.com/entry/2017/02/15/134755 1.0 100%