差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/10] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/10] – [解法] ikatakos | ||
|---|---|---|---|
| 行 188: | 行 188: | ||
| ==データ== | ==データ== | ||
| - | $DP[i][j]=i$人目までの子供に、$j$ 個の飴を配るパターン数 | + | $DP[i][j]=i$人目までの子供に、合計 |
| として考える。$j$ の範囲は $0～K$ で用意することになる。 | として考える。$j$ の範囲は $0～K$ で用意することになる。 | ||
| 行 211: | 行 211: | ||
| | | ||
| - | この各遷移の各 $j$ につき、$DP[i-1]$ の参照と $DP[i]$ への加算が発生するので、$i-1$ から $i$ への遷移で計算が $K \times a_i$ 回発生することになる。それぞれ上限 $10^5$ なので、間に合わない。 | + | この、○個配ったときの各遷移の各 $j$ につき、$DP[i-1]$ の参照と $DP[i]$ への加算が発生するので、$i-1$ から $i$ への遷移で計算が $K \times a_i$ 回発生することになる。それぞれ上限 $10^5$ なので、間に合わない。 |
| ===圧縮=== | ===圧縮=== | ||
