差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:contest_history:atcoder:2019:0504_agc033 [2019/05/10] – ikatakos | programming_algorithm:contest_history:atcoder:2019:0504_agc033 [2019/05/10] – ikatakos | ||
---|---|---|---|
行 59: | 行 59: | ||
まず、$k=0$ の時を埋める。 | まず、$k=0$ の時を埋める。 | ||
- | $DP1[a][b][a]$ は、$(a, | + | $DP1[0][a][b][a]$ は、$(a, |
- | $DP1[a][b][c]$ は、まず $(a, | + | $DP1[0][a][b][c]$ は、まず $(a, |
続いてDPの遷移を考える。2段階で更新する。まず、DP1を使ってDP1を、DP2を使ってDP2を暫定更新する。次に、双方の情報を合わせてDP1、DP2を修正更新する。 | 続いてDPの遷移を考える。2段階で更新する。まず、DP1を使ってDP1を、DP2を使ってDP2を暫定更新する。次に、双方の情報を合わせてDP1、DP2を修正更新する。 |