koba-e964 https://blog.hatena.ne.jp/koba-e964/ koba-e964の日記 https://koba-e964.hatenablog.com/ 考察・実装合計で 2 時間かかった上に、無駄な実装をしてしまった。 Problem - D - Codeforces 問題 長さ n の数列 h が与えられる。1 番目の要素から n 番目の要素まで離散的ジャンプだけを使って移動したい。i 離散的であるとは、max(h[i+1], ..., h[j-1]) max(h[i], h[j]) が成立することをいう。離散的ジャンプの最小回数を求めよ。制約 2 1 解法 愚直な O(N^2) DP (dp[i] := i から n までの最短手数) を考える。i から j へジャンプできるのは j が i+1 から貪欲に取った単調増加列か単調減少列に含… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkoba-e964.hatenablog.com%2Fentry%2F2020%2F09%2F21%2F110149" title="Codeforces Round #669 (Div. 2) D. Discrete Centrifugal Jumps - koba-e964の日記" 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 2020-09-21 11:01:49 rich https://koba-e964.hatenablog.com/entry/2020/09/21/110149 1.0 100%