P1077 [NOIP 2012 普及组] 摆花

P1077 [NOIP 2012 普及组] 摆花 - 洛谷

这道题是 “多重背包 + 有顺序限制” 的经典变形，下面我们一步步详细讲解题意、解法思路和你的代码逻辑。

✅【题意解析】

你要用 n 种花，总共摆放 m 盆。

• 每种花最多摆放 a[i] 盆。

• 同种花必须连在一起。

• 不同种花 必须按照编号从小到大 摆放。

• 求一共有多少种不同的摆放方案（最终方案只看数量和种类组合，顺序是固定的）。

状态转移方程

对于第 i 种花，我们最多可以用 a[i] 盆。

枚举摆的总数 j 从 m 到 0，再枚举这第 i 种花使用的数量 k（从 1 到 min(j, a[i])）：

for (int i = 1; i = 0; j--) // 枚举总盆数（必须倒着） for (int k = 1; k <= min(a[i], j); k++) // 枚举当前花使用数量 f[j] = (f[j] + f[j - k]) % mod;

为什么 j 要倒着枚举？

• 避免第 i 次更新时，把当前 i 次生成的 f[j-k] 再次用来更新，导致重复计算。