drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder550点 ABC-F 黄色diff 体力や燃料がある一定以上必要になる設定の問題 数直線上のN点の問題 DP シーケンシャルDP 操作を逆順に見る DP状態:ナップサック 最小コスト 解空間:O(2^N)通りの選択肢 制約:数値が10^6以下 最適化問題 NoviSteps3D 少し重たかった。でもいい問題。JOI にありそう。 問題へのリンク 問題概要 数直線上に 箇所の燃料補給所がある。 番目の補給所は次のようになっている。 座標 にある 補給すると、現在の HP が であるとき、HP が になる (コストとして を支払う) 今、高橋君は座標 を HP が である状態で出発して、座標 の地点を訪れて、座標 の地点へと引き返す。なお、1 進むと HP が 1 減少する。 注意したいこととして、どの補給所も高々 1 回しか使えない。つまり、行きの途中で使用した補給所は、帰りには使えない。 帰ってくるまでに一度も HP が負にならないようにするための最小コストを求めよ … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2023%2F09%2F17%2F002721" title="AtCoder ABC 320 F - Fuel Round Trip (3D, 黄色, 550 点) - けんちょんの競プロ精進記録" 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.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2023-09-17 00:27:21 rich https://drken1215.hatenablog.com/entry/2023/09/17/002721 1.0 100%