T28702: 合理的饭票设计

dfs, dp, http://cs101.openjudge.cn/practice/28702/

以前大学食堂都使用餐票吃饭，每顿饭菜钱可以为1角，2角，...，最多为n角。如果规定每次吃饭最多只能使用k张餐票，是否可以设计m种不同面值的餐票，使得餐票从1开始可以连续覆盖的面值范围恰好为 1 - n（角）？满足上述条件的方案有多少？

假设 n 的值不超过500，饭菜钱单位为角。例如， m=3, k=2, n=8, 则，面值为：{1,3,4} 恰好覆盖 1,2,...,8，此时，1角只需要1张面值为1的即可，2角需要2张面值为1的，3角只需要1张面值为3的，4角只需要1张面值为4的，5角需要1张面值为1的再加上1张面值为4的，6角需要2张面值为3的，7角需要1张面值为3再加上1张面值为4的，8角需要2张面值为4的。即：只需要2张面值的饭票即可覆盖1-8的范围（注意：一定是连续覆盖）。除了这三种面值之外，再没有其他方案的面值。因此，这样的方案有1种。

若m=3, k=2, n=9, 则不存在面值组合，因此，为0种方案。

若m=3, k=2, n=6,则有 {1,2,3}，{1,2,4}和{1,3,5}共3种。

若m=3, k=2, n=5, 则不存在，因此，为0种。

输入

第1行输入正整数 P, 表示后面有 P行后面的P行分别为 m,k,n,其间以空格间隔

输出

对应输出 P行，若不存在 m 种面值的饭票，则输出0，若有，则输出方案数。

样例输入

样例输出

提示

tags: dfs, dp 注意代码运行效率，可以注意对一些重复操作进行优化。

来源

2024 TA-xjk

这是一个经典的组合优化问题，属于“邮资问题”（Postage Stamp Problem）的变种。我们需要找到所有包含 $m$ 种面值、且包含面值 1 的集合，使得使用不超过 $k$ 张饭票能构成的连续面值范围恰好是 $1$ 到 $n$ 。

算法思路

搜索框架 (DFS)：
- 由于面值集合必须包含 1，我们从集合 ${1}$ 开始搜索。
- 我们需要再选择 $m - 1$ 个不同的面值。
- 为了避免重复并保证面值递增，我们规定下一个选取的面值 $v_{n e x t}$ 必须大于当前已选面值的最大值 $v_{l a s t}$ 。
剪枝与候选范围：
- 假设当前已选面值集合能覆盖的连续范围是 $1$ 到 $R$ 。
- 下界： $v_{n e x t} > v_{l a s t}$ 。
- 连续性约束（上界）：为了保证新集合能从 1 开始连续覆盖，新加入的面值 $v_{n e x t}$ 不能太大，导致出现断层。当前能覆盖到 $R$ ，那么 $R + 1$ 必须能被新集合覆盖。由于 $R + 1$ 不能由旧集合覆盖，必须用到新面值 $v_{n e x t}$ 。如果 $v_{n e x t} > R + 1$ ，那么 $v_{n e x t}$ 加上任何非负数组合都 $\geq R + 2$ ，无法构成 $R + 1$ 。因此，必须满足 $v_{n e x t} \leq R + 1$ 。
- 目标约束（强剪枝）：我们的目标是覆盖范围恰好为 $n$ 。
  - 如果当前 $R > n$ ，说明已经覆盖了 $n + 1$ 及以上，该路径无效，回溯。
  - 如果当前 $R == n$ 且已选够 $m$ 张，这是一个解。
  - 在选择 $v_{n e x t}$ 时，如果 $v_{n e x t} > n$ ，它对填补 $1 \dots n$ 的空缺没有帮助，且可能导致范围延伸更远，通常可以直接忽略（实际上 $v_{n e x t} \leq R + 1$ 且 $R \leq n$ 已经隐含了 $v_{n e x t} \leq n + 1$ ）。
状态维护与更新 (DP)：
- 我们需要维护一个 dp 数组，dp[x] 表示凑出面值 x 所需的最少饭票张数。
- 初始状态：只有面值 1 时，dp[x] = x (只要 $x \leq k$ )。
- 当加入新面值 $v$ 时，更新 dp 数组：对于 $j$ 从 $v$ 到 $n + 1$ ：dp[j] = min(dp[j], dp[j-v] + 1)。这里类似于完全背包问题，但我们只关心使用的硬币数量是否 $\leq k$ 。
- 更新完 dp 后，重新扫描 dp 数组，找到新的最大连续覆盖值 $R_{n e w}$ （即满足 dp[i] <= k 的最大连续 $i$ ）。
- 注意：为了判断范围是否恰好为 $n$ ，我们需要检查 $n + 1$ 是否可达。如果 dp[n+1] <= k，说明范围超过了 $n$ ，不符合要求。

Python 代码实现

python

import sys

# 增加递归深度，防止深层搜索报错
sys.setrecursionlimit(3000)


def dfs(count, last_val, current_R, current_dp, m, k, n):
    """
    count: 当前已选面值数量
    last_val: 上一个选定的面值
    current_R: 当前集合能连续覆盖的最大值 1..current_R
    current_dp: 当前的DP表，current_dp[i] 表示凑成 i 所需的最少票数
    """

    # 剪枝：如果当前覆盖范围已经超过 n，说明不仅覆盖了 1..n，还覆盖了 n+1，不符合"恰好"
    if current_R > n:
        return 0

    # 如果选够了 m 张票
    if count == m:
        # 检查是否恰好覆盖到 n (即 1..n 可达，n+1 不可达)
        return 1 if current_R == n else 0

    total_solutions = 0

    # 确定下一个面值的搜索范围
    # 下一个面值 v 必须满足：
    # 1. v > last_val (保持递增，避免重复)
    # 2. v <= current_R + 1 (保证连续性，否则 R+1 无法构成)
    # 3. v <= n (因为如果 v >= n+1，一旦选中，R 至少会延伸到 n+1，导致 R > n 失败)

    start_node = last_val + 1
    end_node = min(current_R + 1, n)

    for v in range(start_node, end_node + 1):
        # 复制并更新 DP 表
        # 由于只需要判断是否覆盖到 n，DP 数组大小只需维护到 n+1
        new_dp = current_dp[:]

        # 完全背包方式更新
        # 只需要更新到 n + 1 即可，超过的部分对于判断"恰好为n"没有帮助
        for j in range(v, n + 2):
            if new_dp[j - v] < k:
                if new_dp[j - v] + 1 < new_dp[j]:
                    new_dp[j] = new_dp[j - v] + 1

        # 计算新的连续覆盖范围
        new_R = current_R
        # 尝试向后延伸 R
        while new_R < n + 1 and new_dp[new_R + 1] <= k:
            new_R += 1

        # 如果新范围超过 n，剪枝
        if new_R > n:
            continue

        # 递归搜索
        total_solutions += dfs(count + 1, v, new_R, new_dp, m, k, n)

    return total_solutions


def solve():
    # 读取所有输入
    input_data = sys.stdin.read().split()
    iterator = iter(input_data)
    num_cases = int(next(iterator))

    for _ in range(num_cases):
        m = int(next(iterator))
        k = int(next(iterator))
        n = int(next(iterator))


        # 边界情况处理
        if m <= 0:
            print(0)
            continue

        # 初始化 DP 数组
        # 大小为 n + 2，用于检查 0..n+1
        # 初始化为大数（表示不可达）
        dp = [10000] * (n + 2)
        dp[0] = 0

        # 初始集合只有 {1}
        # 计算 {1} 能构成的范围
        # 能构成 x 需要 x 张票，只要 x <= k
        limit_with_1 = min(k, n + 1)
        for i in range(1, limit_with_1 + 1):
            dp[i] = i

        current_R = limit_with_1

        # 此时如果 k >= n + 1，说明仅用 {1} 就能覆盖到 n+1，
        # 无论后面加什么面值，范围都至少是 n+1，因此不可能"恰好为 n"
        if current_R > n:
            print(0)
            continue

        # 如果只需要 1 种面值
        if m == 1:
            print(1 if current_R == n else 0)
            continue

        # 开始 DFS
        # 初始 count=1 (已选{1}), last_val=1
        ans = dfs(1, 1, current_R, dp, m, k, n)
        print(ans)


if __name__ == '__main__':
    solve()

T28702: 合理的饭票设计 ​

T28702: 合理的饭票设计