ツバサの備忘録

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

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

動的計画法(DP)

問題
 提出コード

解法

現在、積まれているブロックの重さの総和を $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}$ の場合、 $j$ を $i$ の上に乗せたほうがよいです。
この条件を式変形すると、 $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です。

感想

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