メモがてら書きます.
問題はこちら
問題概要
長さの数列を作る.各には個の選択肢があり,を選ぶとのコストがかかる.さらに,各についてのコストが追加でかかる.コストの総和の最小値を求めよ.解説
複数の選択間にコストがある+制約的にProject Selection Problemっぽい.Project Selection Problemは最小カット(最大流)で解ける.以下のグラフで頂点をS or Tに分割するカットを考える.
これはの場合において以下のように辺にコストを割り当てると,以下の各カットが各選択に対応する.
しかし,以下のようなカットも可能になってしまうので
以下のようにコストの辺を張れば,最小カットは上の通りのうちどれかになる.
これでコストのグラフ表現はできたのでコストのグラフ表現を考える.
間のコストが以下の表のようになっているとする().実は,この表がMonge性を満たしていればグラフ表現可能.今回の関数がMonge性を満たすことはすぐに分かる.
これらの操作はMonge性を満たす行列に適用してもMonge性は保存される.基本操作
具体的にグラフを構築していく.
行目に対して各要素から成分の値を引く.
列目に対して各要素から成分の値を引く.
3つ目の"基本操作"は累積和のようになっているので累積和の逆をして各成分に加える値を計算する.3つ目の"基本操作"にとして適用
が負になることがあるが,をから引けばいい.ただし最終的な答えにを足す必要がある.
Project Selection Problem(燃やす埋める問題)に関する基礎知識は以下の記事を参考にしてください.
kanpurin.hatenablog.com