moistx https://blog.hatena.ne.jp/moistx/ Logfiles https://logfiles.hatenablog.com/ まずは蟻本から Intervals (POJ No.3680) 個の重み付き閉区間がある。i番目の区間はをカバーし、重みを持つ。この中から個より多くの区間で覆われている点が存在しないように幾つかの区間を選び、重みの和を最大化せよ。 の場合、個の区間から互いに交差しないように選んだときの重みの和の最大値を求める問題（＝区間グラフの最大重み安定集合問題, 重み付き区間スケジューリング） 区間グラフの最大安定集合問題 DPの日本語の式 (1) DPの数式 (2) DPのグラフ的解釈 (3a, 3b) このようなグラフの (4) 問題を解いていると考えることができる。 どの点もK個より多くの区間で覆わ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Flogfiles.hatenablog.com%2Fentry%2F2016%2F09%2F21%2F225500" title="重み付き区間スケジューリング - Logfiles" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://chart.apis.google.com/chart?cht=tx&chl=N Hatena Blog https://hatena.blog 2016-09-21 22:55:00 rich https://logfiles.hatenablog.com/entry/2016/09/21/225500 1.0 100%