差分
このページの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 | ||
|---|---|---|---|
| 行 43: | 行 43: | ||
| k=6 | k=6 | ||
| | | ||
| - | 文字列例1 | + | 文字列例1 |
| 条件1 | 条件1 | ||
| 条件2 | 条件2 | ||
| 行 50: | 行 50: | ||
| 条件5 | 条件5 | ||
| | | ||
| - | 文字列例2 | + | 文字列例2 |
| 条件1 | 条件1 | ||
| 条件2 | 条件2 | ||
| - | 条件3 | + | 条件3 |
| 条件4,5 略 | 条件4,5 略 | ||
| 行 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は加算後の値）で求められるようになる。 | ||
| - | 「DP配列で、決定済みの部分の数値がいじられる」ことにちょっと抵抗感があるが、この方法で効率的に更新を行える。 | + | 個人的に「DP配列で、決定済みの部分の数値がいじられる」ことにちょっと抵抗感があるが、この方法で効率的に更新を行えるのだから仕方ない。 |
| ここで、現在の $k$ を範囲に含む条件のスコアのみが、過不足無くDPに反映された状態を保たないといけない。 | ここで、現在の $k$ を範囲に含む条件のスコアのみが、過不足無くDPに反映された状態を保たないといけない。 | ||
| 行 107: | 行 107: | ||
| 条件5 | 条件5 | ||
| - | それには、以下の処理を行うとよい。 | + | 加算していたのを元に戻すには、同じ範囲に $-A_i$ を加算すればよい。 |
| - | + | ||
| - | * $k$ から新しく範囲となる（$k=L_i$）条件に対して、$DP[1]～DP[L_i-1]$ に $A_i$ を加算する | + | |
| - | * $k$ で範囲が終了する（$k=R_i$）条件は、加算していたものを元に戻す（$DP[1]～DP[L_i-1]$ | + | |
| まとめると、$k$ を1つずつ見て、$DP[k]$ を小さい方から確定させていく過程で、 | まとめると、$k$ を1つずつ見て、$DP[k]$ を小さい方から確定させていく過程で、 | ||
