12/31 PKU

2964 Tourist

たぶん某国のぱないアルゴリズマーは関係ない。マップ上で、左上の点から右下の点まで行ってまた帰ってくる。いくつかのマスは通れない。いくつかのマスには面白いものがある。上下左右に動けるが、経路は最短でないといけない。面白いマスをできるだけ多く通るとき最大でいくつ通れるか。行き帰りに２回通ったとしてもそれは１回にしかならない。

よく分からないので、最小費用流を使って無理やり通した。
各マスについて、頂点a, a'を対応させ、a->bへ移動できるときa'->bの辺を張っておく。a->a'にコスト1、流量無限の辺を張り、さらにそのマスに面白いものがあるならa->a'にコスト0、流量1の辺を張る。そして左上->右下'で流量2の最小費用流を解くと、(W+H-1)*2 - (mincost_flow) が答えになっている。

3635 Full Tank?

町とそれらを結ぶ道のリストが与えられる。各町では燃料をそれぞれの値段で売っている。道は通るのにそれぞれいくらかの燃料を消費する。燃料がCまで入る車を使って、町sから町eまで移動するのにいくらかかるか（最初燃料は入っていない）求めるクエリをQ個処理せよ。

自前でヒープ書いて普通にDijkstraしたら通った

3216 Repairing Company

Q個の場所がある町に修理会社がある。修理会社のある日の仕事表（仕事場所、仕事を始める時間、仕事にかかる時間）と、場所の間の距離の表が与えられる。何人の修理人が必要か。

グラフを適当に作成して、1422と同じ事をやる。

2127 Greatest Common Increasing Subsequence

2つの数列の共通部分列で、単調増加になっているもののうち最も長いものを答えよ。

DP。問題文中にM<=500とあるがそれを鵜呑みにするとWAするひどい問題。