komiyam https://blog.hatena.ne.jp/komiyam/ komiyamの日記 https://komiyam.hatenadiary.org/ TopCoder 問題概要 [0,distance(区間を考える。この区間内に人がN( 考えたこと 一目二分探索。 最初に人の座標をソートしておけば、左端から順に考えられるのでよさげ。 dp[p] = ([0,p]をカバーするのに必要な最小コスト)とすればいけそう。 書く、合わない。これじゃDAGにならないんだからそりゃそうだ。 dp[i][p]としてi-1人目まで処理し終えた時点で…という風に書き換える。 これでも合わない。何で？ 更新する範囲と交差の判定とDPテーブルの初期化間違えてた。修正。通った。 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkomiyam.hatenadiary.org%2Fentry%2F20110823%2F1314043603" title="SRM 370 500pt: ConnectTheCities - komiyamの日記" 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 2011-08-23 05:06:43 rich https://komiyam.hatenadiary.org/entry/20110823/1314043603 1.0 100%