蟻本の練習問題埋め2-3(3)
DP（少し考察を要する問題）
POJ 1065 - Wooden Sticks
http://poj.org/problem?id=1065
問題
n個の棒を処理する。
i番目の棒は長さがl[i]で重さがw[i]である。
最初の棒を処理する場合、セットアップに1分かかる。
棒iを処理した後に棒jを処理する場合
l[j]>=l[i], w[j]>=w[i]
を満たすならセットアップに時間はかからず、満たさない場合はセットアップに1分かかる。
最適な順番で棒を処理していくとき、セットアップにかかる時間の最小値を求めよ。
制約
n <= 5000
l[i],w[i] <= 10000
解法
棒には半順序が成り立つ。
よってDAGを構成することが出来て、この問題はDAGの最小パス被覆を求める問題になる。
DAGの最小パス被覆といえば二部マッチングだが、計算量的に厳しい。
ここで、Dilworthの定理というものがあり、
「最小パス被覆=反鎖の大きさの最大値」
が成り立つ。
反鎖とは、全ての要素間について順序が成り立たない部分集合である。
そのような集合の最大サイズがこの問題の答えとなる。
l[i]で昇順ソートした場合、i
よってw[i]の狭義最長減少列を求めれば良い。
これはLISと同様にDPすれば、O(n^2)もしくはO(nlogn)。
ちなみにgreedyでも解ける。
Dilworthの定理はOUPCのC問題（AOJ2352）で登場している。
POJ 1631 - Bridging signals
http://poj.org/problem?id=1631
O(nlogn)でLISやるだけ
POJ 3666 - Making the Grade
http://poj.org/problem?id=3666
問題
要素数nの数列a[i]が与えられる。
a[i]を修正して広義単調増加もしくは広義単調減少な数列b[i]にする。
このときコストの最小値を求めよ。
制約
n<=2000
a[i]<=10^9
答えはintに収まる
解法
a[i]それぞれについて、a[i]の中で現れている値に修正することを考えれば良い。
a[i]をソートしたものをc[i]とする。
dp[i+1][j] = a[i]までをc[j]以下で並べるときの最小コスト
でDPする。
を利用すればO(1)で更新できる。
POJ 2392 - Space Elevetor
http://poj.org/problem?id=2392
問題
K種類のブロックがあり、これを１列に積み上げる。
i種類目のブロックは高さh[i]、個数c[i]、存在しうる最大高度a[i]である。
このとき、積み上げられたブロックの高さの最大値を求めよ。
制約
K<=400
a[i]<=40000
c[i]<=10
h[i]<=100
解法
a[i]の昇順にブロックを使っていくことにより、答えとなる最大値を達成することが出来る。
よってa[i]でソートし、ナップサック問題と同様にDPすることで解ける。
O(Ka)またはO(Kac)
POJ 2184 - Cow Exhibition
http://poj.org/problem?id=2184
問題
S[i]とF[i]という値を持つ牛がN匹いる。
この牛から何匹か選んで
��S[i]+��F[i]
を最大にしたい。
ただし、��S[i]>=0, ��F[i]>=0を満たさなければならない。
制約
N<=100
-1000<=S[i],F[i]<=1000
解法
dp[i][j] = i番目の牛までを考えたとき、��S[i]=jとなるときの��F[i]の最大値
とすれば、答えは
max{ j+dp[N][j] | dp[N][j]>=0 }
となる。
��S[i]<=10^5なので、jとしては10^5までを考えれば良い。
- 初期値 : dp[i][j]=-INF、dp[0][0]=0
- dp[i+1][j] = dp[i][j]
- dp[i+1][j+S[i] ] = max(dp[i+1][j+S[i] ], dp[i][j]+F[i])
を用いて更新する。
S[i]が負であるような牛iを使うことに対応させるため、S[i]が大きい順に使うようにすると良い。
あと多分メモリが足りないのでdp配列は使いまわす。
