差分
このページの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/26] – [解法] ikatakos | ||
|---|---|---|---|
| 行 41: | 行 41: | ||
| なのだが、$k-1$ 文字目以前に既に加算していた場合は新たには加算されない。 | なのだが、$k-1$ 文字目以前に既に加算していた場合は新たには加算されない。 | ||
| - | k=6 | + | k=6 |
| - | 文字列 | + | 1 2 3 4 5 6 7 8 |
| - | 条件1 | + | 文字列例1 |
| - | 条件2 | + | 条件1 |
| - | 条件3 | + | 条件2 |
| - | 条件4 | + | 条件3 |
| - | 条件5 | + | 条件4 |
| + | 条件5 | ||
| | | ||
| - | 文字列 | + | 文字列例2 |
| - | 条件1 | + | 条件1 |
| - | 条件2 | + | 条件2 |
| - | 条件3 | + | 条件3 |
| + | | ||
| $k$ 文字目より前で最後に''' | $k$ 文字目より前で最後に''' | ||
| 行 248: | 行 249: | ||
| === 初期条件 === | === 初期条件 === | ||
| - | -1など、重さ $j$ が処理済/未処理であることが区別できる値で埋めておく | + | $DP[0][0]=0$ |
| + | |||
| + | 他は、重さ $j$ が実現可能/不可能であることが区別できるよう、-1など正しい重さになり得ない値で埋めておく | ||
| - | DP[0][0]=0 | ||
| === 優先順位 === | === 優先順位 === | ||
