DP及优化题记

• 这里记录一些见到过的动态规划及常见优化，备忘用。

• 由于笔者时间不足，或许会写得很简略。

[ARC059E] キャンディーとN人の子供

• 前缀和优化DP

一个拆贡献的想法是单独考虑每个人的贡献。

设 f[i][j] 表示前 $i$ 个人发了 $j$ 颗糖的答案。

所以贡献应当是每一个分开计算。

然后计算的方法就是相当于把这个人的这一项提出来，剩下的部分进行求和。

式子 :

$$f[i][j] = \sum_{k=0}^j f[i-1][j-k] \left ( \sum_{x = a_i}^{b_i} x^k \right )$$

显然答案是 f[n][c]

枚举当前(第 $i$ 个)人获得了 $k$ 块糖果，那么新的贡献是前边人的贡献乘上他的贡献。

为什么能这么计算呢？

显然小编也不会，所以小编才在补NOIp2021T2时回来翻这题。