差分
このページの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～Li の範囲に加算しておいてやる。 | + | あらかじめ、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 | ||
| - | それには、以下の処理を行うとよい。 | + | 加算していたのを元に戻すには、同じ範囲に −Ai を加算すればよい。 |
| - | + | ||
| - | * k から新しく範囲となる（k=Li）条件に対して、DP[1]～DP[Li−1] に Ai を加算する | + | |
| - | * k で範囲が終了する（k=Ri）条件は、加算していたものを元に戻す（DP[1]～DP[Li−1] | + | |
| まとめると、k を1つずつ見て、DP[k] を小さい方から確定させていく過程で、 | まとめると、k を1つずつ見て、DP[k] を小さい方から確定させていく過程で、 | ||
