AOJ2090 Repeated Subsequences
問題
Repeated Subsequences | Aizu Online Judge
文字列が与えられる。適当な位置で分割したとき、最長共通部分列をとる。
最適な位置で分割したときの最長共通部分列となる文字列を出力せよ。
LiveArchive 6905 Two Yachts
問題
https://icpcarchive.ecs.baylor.edu/external/69/6905.pdf
2隻の船がある。また、(船の運用期間, 得られる金額) のペアで表された企画が個与えられる。
2隻の船だけを用いて運用できるようなスケジューリングをして、得られる金額の総和を最大化せよ。
同じ企画を2度以上採用することはできない。
LiveArchive 6904 Travel Card
問題
何日目に対して、バスに乗る回数と電車に乗る回数が与えられる。
バス、電車それぞれに1回乗る券の他に、
1日バス乗り放題券、1日バス・電車乗り放題券
7日バス乗り放題券、7日バス・電車乗り放題券
30日バス乗り放題券、30日バス・電車乗り放題券
が存在する。それぞれ値段が決まっている。
日間のバスと電車の乗る回数の予定が与えられるので、費用を最小化せよ。
2-SAT
解いたことあるような気がする問題
重み付き区間スケジューリング
まずは蟻本から
の場合、
個の区間から互いに交差しないように選んだときの重みの和の最大値を求める問題（＝区間グラフの最大重み安定集合問題, 重み付き区間スケジューリング）
区間グラフの最大安定集合問題
- DPの日本語の式 (1)
- DPの数式 (2)
- DPのグラフ的解釈 (3a, 3b)
- このようなグラフの (4) 問題を解いていると考えることができる。
どの点もK個より多くの区間で覆われない ＝ (4)
このようなグラフにおけるから
への１つの最短路のコストは、
の場合のDPで得られた値の符号を反転したものになる。
このグラフで、の重みをつけた辺をパスに含むことが区間
を選ぶことに対応する。したがって、この辺の容量を1とし、他の辺の容量を∞としたネットワークを考えれば、その流量
の
フローは
個の集合の重みの和に対応する。よって、最小費用流のアルゴリズムで解くことができる。グラフに負の辺が含まれることより、負の辺に予め目一杯流しておく方式を取る。
Data Structures and Network Algorithms: 8.4 最小費用流
増加パスの概念は、より一般的なネットワークフローの問題に拡張できる。
Gを各辺[u, w]が容量とフローの1ユニットごとのコストcost(v, w)を持つグラフとする。
簡単のため、コストを歪対称的(skew symmetric)とする。すなわち (1)
フローfのコストは、(2)
フローは同じ流量を持つ全てのフローの中で最小のコストを持つとき、(3) であるという。
最小費用流問題とは、(4) である。
定理8.11
フローfは、(5)、またそのときに限り、費用最小である。
定理8.12
fを費用最小のフローとする。このとき (6) 、fにフローを増加して得られた (7) である。
続きを読む補題8.4
費用最小増加法では、一連の増加パスは非減少のコストを持つ。
