蟻本の練習問題埋め2-3(1)
DP
まだ楽
POJ 3176 - Cow Bowling
POJ 3177 - Sumsets
http://poj.org/problem?id=2229
nを超えない2の累乗使ってDP。
普通に書いたらTLEして定数倍高速化したら通った。
POJ 2385 - Apple Catching
http://poj.org/problem?id=2385
問題
リンゴの木が一直線に並んでいる。
T分に渡り、１分ごとにある木からリンゴが落ちてくる。
i分後にリンゴが落ちる木の番号をa[i]とする（問題文には変数名なし）。
i分後にa[i]番目の木の下にいた場合、リンゴを１個取ることが出きる。
初め１番目の木の下にいるとき、できるだけ沢山のリンゴを取りたい。
木と木の間の移動時間は無視できる。
しかしW回を超えて移動することは出来ない。
この時取得可能なリンゴの最大値を求めよ。
制約
T<=1000
W<=30
a[i]の制限は不明
解法
a[i]の値の範囲がわからないので、取り敢えずmapを使ってそれぞれの木にIDを割り当てる。
dp[i][j] = j回移動してi番目に位置するとき取得したリンゴの最大値
という配列を使ってDPする。
O(T^2*W)
POJ 3616 - Milking Time
http://poj.org/problem?id=3616
問題
今後N時間にわたってミルクを沢山取りたい。
ミルクをとれるタイミングはM回あり、開始時間s[i]、終了時間t[i]、そのときに取れるミルクの量e[i]が決まっている（変数名長かったから短縮）。
ミルクを取り終わってから次に取り始めるまでR時間休まなければならない。
例えばR=2の場合、時間1~2で取った後、時間3~5では取れないが時間4~6とかでは取れる。
取れるミルクの最大量を求めよ。
制約
N<=10^6
M<=1000
s[i]
解法
s[i]の値で区間をソートする。
これにより、j
POJ 3280 - Cheapest Palindrome
http://poj.org/problem?id=3280
問題
M文字の文字列sが与えられるので、文字を挿入するか削除するかして回文にしたい。
各文字を挿入する時と削除するときのコストが与えられる。
与えられた文字列を回文にするコストの最小値を求めよ。
制約
M<=2000
コスト<=10000
解法
回文を作るときにある文字に対応する文字が無いとき、挿入か削除どちらをしても良い。
つまりコストが小さい方を使えば良い。
dp[i][j] = s[i..j]を回文にするときの最小コスト
とする。
s[i]==s[j]なら、dp[i][j]=dp[i+1][j-1]
s[i]!=s[j]なら、
- (s[i]を処理するコスト) + dp[i+1][j]
- (s[j]を処理するコスト) + dp[i][j-1]
のminを取る。
メモ化再帰が楽だった。
