差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/11] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/11] – [解法] ikatakos | ||
---|---|---|---|
行 212: | 行 212: | ||
この、○個配ったときの各遷移の各 $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$ なので、間に合わない。 | ||
+ | |||
+ | 擬似コード | ||
+ | for i in 1..N: | ||
+ | for k in 0..a: | ||
+ | for j in 0..K: | ||
+ | dp[i][j+k] += dp[i-1][j] | ||
===圧縮=== | ===圧縮=== |