刷题笔记合集🔗

分月饼

问题描述

中秋节，公司分月饼， 个员工，买了 个月饼，，每个员工至少分 个月饼，但可以分多个。

• 单人分到最多月饼的个数是 ，单人分到第二多月饼个数是 ，。
• 单人分到第 多月饼个数是 ，单人分到第 多月饼个数是 ，。

问有多少种分月饼的方法？

输入格式

每一行输入 ，表示 个员工， 个月饼，。

输出格式

输出有多少种月饼分法。

样例输入

2 4

3 5

3 12

样例输出

2

2

6

数据范围

题解

这道题的本质是要把 个相同的月饼分给 个人，每人至少分到 个，而且当我们把分到的数量从多到少排序后，任意相邻两个人所分数量之差不能超过 。交换顺序视为同一种分法，例如 和 只算一次。

我们可以按以下思路来拆解并转化问题：

1. “先给每人预分 个”——这样保证了每个人至少 ，共消耗 个月饼，剩下
   
   个月饼。
2. 设新的份额为
   
   且相邻差满足
   
3. 再引入“差分”变量
   
   这样每个 就相当于“重量为 的物品”，而且每种最多能选 件。最后还剩下的 ，可以看作“重量为 的物品”，可取任意件。要凑出总重量 ，就变成了一个典型的有界背包（多重背包）问题。
4. 用一维数组 dp[s] 表示用前面那些“差分物品”凑出重量 的方法数。初始 dp[0]=1，每次枚举“物品种类” ，再枚举容量 和选取数量 ，更新 dp[s+i*k] += dp[s]。
5. 上述过程结束后，dp[s] 就是所有差分部分凑成 的方案数。最后再枚举 最小份额 （即“重量为 的物品”取 件），只要满足
   
   就把所有 dp[s] 累加起来即可。

举个小例子帮助理解：

• 当 时，先预分 个，还剩 。
• 差分种类有 ，都最多取 件。我们做背包后得到 dp=[1,1,2]，表示凑成 的方法数分别是 。
• 最后枚举 （）时只看 dp[2]=2； 时 不合法。所以结果是 种，对应原分法 和 。

关键技巧与数据结构：

• 差分思想把不降序且相邻差限制转成“有界物品背包”
• 一维多重背包 DP 数组节省空间
• 最后再枚举最小份额

时间复杂度：背包主体是 ，再加上枚举最小份额 ，整体约 。当 时，最多 级别操作，完全可以在毫秒级内通过。

虽然也可以用深度优先加剪枝的方式暴力枚举，但在最坏情况下会很慢。上述差分＋多重背包的做法最优且代码简洁。

参考代码

• Python

import sys

def count_ways(m, n):
    # 剩余月饼 N = n - m（每人预分 1 个）。
    N = n - m
    # dp[s] 表示用差分物品凑出重量 s 的方法数。
    dp = [0] * (N + 1)
    dp[0] = 1
    # 对于差分 d_i，对应重量 i，数量上限为 3。
    for i in range(1, m):
        nxt = [0] * (N + 1)
        for s in range(N + 1):
            v = dp[s]
            if v == 0:
                continue
            # 选取 0 至 3 件重量为 i 的物品。
            for k in range(4):
                ns = s + k * i
                if ns > N:
                    break
                nxt[ns] += v
        dp = nxt
    # 枚举最小差分 t 并累加结果。
    ans = 0
    for t in range(0, N // m + 1):