重み付き区間スケジューリング

まずは蟻本から

Intervals (POJ No.3680)

$N$ 個の重み付き閉区間がある。i番目の区間は $(a_i, b_i)$ をカバーし、重み $w_i$ を持つ。この中から $k$ 個より多くの区間で覆われている点が存在しないように幾つかの区間を選び、重みの和を最大化せよ。

$K = 1$ の場合、 $N$ 個の区間から互いに交差しないように選んだときの重みの和の最大値を求める問題（＝区間グラフの最大重み安定集合問題, 重み付き区間スケジューリング）

区間グラフの最大安定集合問題

DPの日本語の式 (1)
DPの数式 (2)
DPのグラフ的解釈 (3a, 3b)
- このようなグラフの (4) 問題を解いていると考えることができる。

どの点もK個より多くの区間で覆われない＝ (4)

このようなグラフにおける $v_0$ から $v_{m-1}$ への１つの最短路のコストは、 $K=1$ の場合のDPで得られた値の符号を反転したものになる。

このグラフで、 $-w_i$ の重みをつけた辺をパスに含むことが区間 $i$ を選ぶことに対応する。したがって、この辺の容量を1とし、他の辺の容量を∞としたネットワークを考えれば、その流量 $K$ の $v_0 - v_{m-1}$ フローは $K$ 個の集合の重みの和に対応する。よって、最小費用流のアルゴリズムで解くことができる。グラフに負の辺が含まれることより、負の辺に予め目一杯流しておく方式を取る。

解答
1. $dp[i] := b_k \le x_i$ であるような区間のみを考えた場合の最大の重み
2. $dp[i] = max(dp[i-1],\ max\{dp[j]\ +\ w_k\ |\ a_k\ =\ x_j\ かつ\ b_k\ =\ x_i\})$
3a. $m$ 個の端点 $x_i$ に対応する頂点 $v_i$ を作る。
3b. $v_{i-1}$ から $v_i$ へコスト0の辺をはり、各区間 $k$ について $a_k\ =\ x_j$ かつ $b_k\ =\ x_i$ であるような $i$ 、 $j$ に対して $v_j$ から $v_i$ へコスト $-w_k$ の辺を張る。
4. 最短路問題
5. 互いに交差しないような区間の集合K個に分割できる