差分
このページの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: | ||
| 優先順位付きナップサック問題。 | 優先順位付きナップサック問題。 | ||
| + | |||
| + | 自分より上のブロックの重さは丈夫さに関わるため、実際のタワーのように下から積み上げるのではなく、上から決めていく。 | ||
| === データ === | === データ === | ||
| 行 246: | 行 248: | ||
| === 初期条件 === | === 初期条件 === | ||
| - | -1など、重さ $j$ が処理済/未処理であることが区別できる値で埋めておく | + | $DP[0][0]=0$ |
| + | |||
| + | 他は、重さ $j$ が実現可能/不可能であることが区別できるよう、-1など正しい重さになり得ない値で埋めておく | ||
| - | DP[0][0]=0 | ||
| === 優先順位 === | === 優先順位 === | ||
| 行 262: | 行 265: | ||
| * $X+w_j \gt s_i$ | * $X+w_j \gt s_i$ | ||
| - | これを移項してXを消去すると、$s_i+w_i \lt s_j+w_j$ となり、重さと丈夫さの和が小さいブロックから上にした方がよいことが分かる。 | + | これを移項してXを消去すると、$s_i+w_i \lt s_j+w_j$ となる。重さと丈夫さの和が小さいブロックから上にした方がよいことが分かる。 |
| === 遷移 === | === 遷移 === | ||
