糖果 - 题目列表

题目描述

有 $N$ 件产品，第 $i$ 件含 $a_i$ 颗糖果；从中选若干件（可空），使所选总数是 $K$ 的倍数，求能达到的最大总数，凑不出则输出 $0$ 。

输入：第一行 $N\ K$ ，接下来 $N$ 行每行一个 $a_i$ 。输出：最大可行总数。数据范围 $N \leqslant 100$ ， $K \leqslant 100$ ， $a_i \leqslant 10^6$ 。

样例输入 5 7 / 1 2 3 4 5，输出 14：选 $2+3+4+5=14$ ，是 $7$ 的倍数且最大。

思路

判断合法性只看总和模 $K$ 的余数，而同一余数下总和越大越好，所以每个余数只保留最大总和。dp[j] 表示总数模 $K$ 余 $j$ 时的最大值，逐件糖果用上一轮的旧表做 0/1 转移 dp[j] = max(dp[j], old[(j - a % K + K) % K] + a)，答案即 dp[0]，复杂度 $O(NK)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 03:53
# update_at: 2026-09-30 03:53

import sys

NEG = -(1 << 60)  # 不可达哨兵：最大合法总和仅 10^8，再叠加一件糖果后仍远小于 0


def best_multiple(candies: list[int], k: int) -> int:
    """返回能带走的糖果总数最大值（必须是 k 的倍数），凑不出 k 的倍数时返回 0。

    dp[j] = 只扫过前面的糖果、且当前总数对 k 取余恰为 j 时能达到的最大总数，
    NEG 表示该余数暂时凑不出来。dp[0] 恒 >= 0（一件都不取的方案），所以它天然
    满足“凑不出就输出 0”，不需要额外兜底。
    """
    dp = [0] + [NEG] * (k - 1)  # 一件都不拿：总数 0，余数 0 可达
    for value in candies:
        r = value % k
        # 每件糖果只有“不取”（保留 dp[j]）和“取”（从余数 (j-r) mod k 转移、总数加 value）
        # 两种去向；右侧整体读旧表，保证同一件糖果不会被取两次。
        dp = [max(keep, dp[(j - r) % k] + value) for j, keep in enumerate(dp)]
    return dp[0]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, k = next(data), next(data)
    candies = [next(data) for _ in range(n)]
    print(best_multiple(candies, k))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:25
 * update_at: 2026-10-05 08:25
 */

/*
 * 同余 0/1 背包：
 * dp[j] 表示已选糖果总数模 K 余 j 时的最大总数。
 * 每件糖果只有“不取”和“取”两种去向。余数转移是环形的（会回绕），
 * 所以每处理一件糖果都先把旧表整体快照，再从 old 转移，保证 0/1 语义。
 */
#include <cstdio>

typedef long long ll;

const int MAXK = 105;
const ll NEG = -(1LL << 60); // 不可达哨兵：最大合法总和仅 10^8，叠一件糖果后仍远小于 0

ll n, k;      // 糖果件数、要求整除的模数
ll dp[MAXK];  // dp[j]：总数模 k 余 j 时的最大总数，NEG 表示该余数暂时凑不出
ll old[MAXK]; // 处理当前糖果前的旧表快照

int main() {
    scanf("%lld %lld", &n, &k);

    dp[0] = 0; // 一件都不取：总和 0，余数 0 可达
    for (ll j = 1; j < k; ++j) dp[j] = NEG;

    for (ll i = 1; i <= n; ++i) {
        ll value;
        scanf("%lld", &value);
        ll r = value % k; // 这件糖果对余数的贡献

        for (ll j = 0; j < k; ++j) old[j] = dp[j]; // 快照，只允许从上一件状态转移

        for (ll j = 0; j < k; ++j) {
            ll from = (j - r + k) % k; // 取这件后余数由 from 回绕到 j
            if (old[from] == NEG) continue;
            if (old[from] + value > dp[j]) dp[j] = old[from] + value;
        }
    }

    // dp[0] >= 0（空集），凑不出 k 的倍数时恰好就是 0，无需额外判断
    printf("%lld\n", dp[0]);
    return 0;
}

糖果

目录

题目描述

思路

参考代码