ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Educational DP Contest / DP まとめコンテスト X - Tower

問題
提出コード

解法

現在、積まれているブロックの重さの総和をGとします。
ここに、2種類のブロックi,jを、どちらの順番で新しくに置くかを考えます。

  • iの方がjより上にくる場合
    G \leqq s_{i} \cap G + w_{i} \leqq s_{j}

  • jの方がiより上にくる場合
    G \leqq s_{j} \cap G + w_{j} \leqq s_{i}

1つめの条件は、結局2つのブロックを乗せることにした時点で満たしていなければならないので、無視します。
ということで、それぞれの条件の2つ目を比較すると、
G \leqq s_{j} - w_{i},G \leqq s_{i} - w_{j}
となり、s_{j} - w_{i}s_{i} - w_{j}のうち大きい順番の方が、Gの許容範囲が大きくなります。
s_{j} - w_{i} \leqq s_{i} - w_{j}の場合、jiの上に乗せたほうがよいです。
この条件を式変形すると、s_{j} + w_{j} \leqq s_{i} + w_{i}となるので、
結局はs_{i} + w_{i}の昇順でブロックを並べると、その順番で上から積んでいくのが最善になります。
あとは、基本的にナップサックと同じで、
dp[i][j] = i番目のブロックまで見て、重さの総和がjになるようなブロックの選び方をしたときの、価値の総和の最大値
として、
dp[i + 1][j] = max(dp[i][j], dp[i][j - w_{i}] + v_{i})
(ただし、j \lt w_{i} もしくはj - w_{i} \gt s_{i}の際はdp[i][j])

を計算すればよいです。
答えは、dp[n][j]の最大値、初期化は全て0です。

感想

この問題で似たような考え方をしたので、あっさりと解くことができました。
が、証明は難しいです…(後付けで考えました)