差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:contest_history:atcoder:2019:0106_educational_dp_4 [2019/02/08] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:0106_educational_dp_4 [2019/02/08] – [解法] ikatakos | ||
---|---|---|---|
行 241: | 行 241: | ||
優先順位付きナップサック問題。 | 優先順位付きナップサック問題。 | ||
+ | |||
+ | 自分より上のブロックの重さは丈夫さに関わるため、実際のタワーのように下から積み上げるのではなく、上から決めていく。 | ||
=== データ === | === データ === | ||
行 257: | 行 259: | ||
ある2つのブロック $i,j$ があり、2つとも使うことを考える。2つの上に積み上がったブロックの重さの総和を $X$ とする。 | ある2つのブロック $i,j$ があり、2つとも使うことを考える。2つの上に積み上がったブロックの重さの総和を $X$ とする。 | ||
- | $i$ を上にすると両方積めるが、$j$ が上だと積めなくなる場合があったとすると、 | + | $i$ を上にすると両方積めるが、$j$ が上だと積めなくなる場合があったとすると、次が同時に成立しているはずである。 |
* $X+w_i \le s_j$ | * $X+w_i \le s_j$ | ||
* $X+w_j \gt s_i$ | * $X+w_j \gt s_i$ | ||
- | となるXが存在するはずである。(与えられたブロックで実現できるかは別として、数値として) | + | これを移項してXを消去すると、$s_i+w_i \lt s_j+w_j$ となる。重さと丈夫さの和が小さいブロックから上にした方がよいことが分かる。 |
- | + | ||
- | これを移項してXを消去すると、$s_i+w_i \lt s_j+w_j$ となり、重さと丈夫さの和が小さいブロックから上にした方がよいことが分かる。 | + | |
=== 遷移 === | === 遷移 === |