EDPC X - Tower

• 問題
• AC

問題文と制約を見て${O}(N \max s_i)$で解くしかないという気持ちになる。順番が固定されていないが、固定されていないと難しすぎるのでその方法を探す。

丈夫さについても重さについても、大きいブロックは下に置いたほうが良いはずなので、まずは$s_i+w_i$で降順にソートするという案を思いつく。実際、それでよいことが証明できる。有効なタワーが与えられたとし、丈夫さと重さが下のブロックから$(s'_1, w'_1), (s'_2, w'_2),..., (s'_k, w'_k)$になっているとする。隣り合うブロックで$s'_i + w'_i \le s'_{i+1} + w'_{i+1}$が成り立つペアがあったとき、ブロック$i$とブロック$i+1$を入れ替えても有効なタワーのままであることが示せれば十分である。

ブロック$i$と$i+1$を入れ替えたとき、$1, ..., i-1$番目と$i+2, ..., k$番目のブロックにかかる重さは変わらず、$i$番目だったブロックにかかる重さは減るので、$i+1$番目だったブロックについてだけ考えればよい。このブロックに以前掛かっていた重さを$G$とすると、新しい配置で掛かる重さは$G+w'_i$になる。ところで$i$番目だったブロックは丈夫さ$s'_i$で重さ$G+w'_{i+1}$に耐えていたので$s'_i - w'_{i+1} \ge G$が成り立つ。$s'_i + w'_i \le s'_{i+1} + w'_{i+1}$から$s'_{i+1} - w'_i \ge s'_i - w'_{i+1} \ge G$が従い、丈夫さ$s'_{i+1}$で$G+w'_i$に耐えられることがわかる。従って、ブロック$i$と$i+1$を入れ替えてもタワーは有効である。$\square$

$s_i+w_i$の降順に並んだタワーだけ考えればよいことがわかったので、あとは端からDPすればよい。$\operatorname{dp}[x][y] :=$ ブロック$1, 2, ..., x$から作れて、耐えられる重さが$y$であるようなタワーの価値の最大値、とする。

$$\operatorname{dp}[x+1][\min(y-w_{x+1}, s_{x+1})] \leftarrow \max (*, \operatorname{dp}[x][y] + v_{x+1})$$ $$\operatorname{dp}[x+1][y] \leftarrow \max(*, \operatorname{dp}[x][y])$$

と遷移すればよい。（$*$は左辺）