Cross the Wall (UVa Live Archive Asia - 2010 Harbin)
問題
無限の長さと高さがある万里の長城がある。万里の長城を通って向こうに行くためには万里の長城に穴を掘るしか無い。人がN人いてそれぞれw*hの大きさである。それぞれの人が通るためには最低でもw*hの穴が開いてなければならない。またw*hの穴を掘るのにはw*hのコストがかかる。K回まで穴を掘って良い時、必要なコストはいくらか？
1<=N<=50000
1<=w,h<=1000000
1<=K<=100
解法
他の人より明らかに小さい人は削除しhの高い順にソートする。次にdequeを用いたDPを行う。穴を掘った回数をキーとしてk個のdequeを用意する。dequeに入れる要素はこれまでに使ったコストとまだ穴を通ってない人でもっと高いhのペアである。初期状態ではk番目のdequeに(0,h[0])を入れておく。各人でk回ループを回して穴を掘った場合にかかるコストを計算し、dequeを更新する。dequeは穴を掘る直前に先頭にある明らかに必要のないものを削除し、dequeにpush_backする直前にも最後尾にある必要のない要素を削除する。これをすることにより普通にDPするよりも計算量を落とすことが出来、O(NK)で計算できる。
