差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 最新のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0106_educational_dp_4 [2019/02/26] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:0106_educational_dp_4 [2019/02/26] – [解法] ikatakos | ||
|---|---|---|---|
| 行 82: | 行 82: | ||
| DP[6] = MAX( DP[1]+A1+A2+A3, | DP[6] = MAX( DP[1]+A1+A2+A3, | ||
| - | あらかじめ、DP配列に、「$k$ を含む条件のスコア」をそれぞれ $1 ～ L_i$ の範囲に加算しておいてやる。 | + | あらかじめ、DP配列に、「$k$ を含む条件のスコア」をそれぞれ $1 ～ L_i-1$ の範囲に加算しておいてやる。 |
| すると、$DP[k]$ は、ただ1つの区間MAXクエリ $\max(DP[1]～DP[k-1])$ （DPは加算後の値）で求められるようになる。 | すると、$DP[k]$ は、ただ1つの区間MAXクエリ $\max(DP[1]～DP[k-1])$ （DPは加算後の値）で求められるようになる。 | ||
