英雄联盟

题意

有 N 个英雄，第 i 个英雄有 K_i 款皮肤，每款皮肤的价格都是 C_i。

如果一个英雄买了 x 款皮肤，那么这个英雄对应的展示方式就有 x 种；如果没买皮肤，就不贡献展示方式。

现在要让“总展示方式数”至少达到 M，求最少花费。

这张表把题意翻成了背包模型：

原题对象	背包含义
一个英雄	一组物品
买 `x` 款皮肤	这组里选一个方案
花费 `x * C_i`	这一方案的代价
展示方式数乘上 `x`	这一方案的收益

思路

先看一个可以直接验证正确性的朴素解：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93#include <bits/stdc++.h>
using namespace std;

static int N;
static long long M;
static vector<int> K, C;
static int limit;
static vector<int> choose_count;
static vector<long long> best;

static long long clamp_mul(long long a, int b) {
    __int128 v = (__int128)a * b;
    if (v > M) {
        return M;
    }
    return (long long)v;
}

static int calc_cost() {
    int cost = 0;
    for (int i = 0; i < N; ++i) {
        cost += choose_count[i] * C[i];
    }
    return cost;
}

static long long calc_ways() {
    long long ways = 1;
    for (int i = 0; i < N; ++i) {
        if (choose_count[i] == 0) {
            continue;
        }
        ways = clamp_mul(ways, choose_count[i]);
    }
    return ways;
}

static bool check() {
    return calc_cost() <= limit;
}

static void dfs(int dep) {
    if (dep == N) {
        if (check()) {
            int cost = calc_cost();
            long long ways = calc_ways();
            best[cost] = max(best[cost], ways);
        }
        return;
    }

    // 第 dep 个英雄可以不买皮肤，或者买 2..K[dep] 款皮肤。
    choose_count[dep] = 0;
    dfs(dep + 1);

    for (int x = 2; x <= K[dep]; ++x) {
        choose_count[dep] = x;
        dfs(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    K.resize(N);
    C.resize(N);
    for (int i = 0; i < N; ++i) {
        cin >> K[i];
    }
    for (int i = 0; i < N; ++i) {
        cin >> C[i];
    }

    limit = 0;
    for (int i = 0; i < N; ++i) {
        limit += K[i] * C[i];
    }

    best.assign(limit + 1, 0);
    choose_count.assign(N, 0);
    dfs(0);

    for (int cost = 0; cost <= limit; ++cost) {
        if (best[cost] >= M) {
            cout << cost << '\n';
            return 0;
        }
    }

    return 0;
}

brute.cpp 把每个英雄买几款皮肤看成一层选择：choose_count[i] 表示第 i 个英雄买的皮肤数量。递归先生成完整计数序列，叶子节点再统计总花费和展示方式数。

这题的关键是把“方式数”当成 DP 的值，而不是把它当成要枚举的对象。

对第 i 个英雄来说，可选方案只有：

不买，展示方式数不变，花费 0
买 2..K_i 款，展示方式数乘上 x，花费增加 x * C_i

买 1 款没有意义，因为它不会增加展示方式数，只会增加花费。

所以这就是一个按英雄分组的背包：

状态	含义
`dp[j]`	花费恰好/不超过 `j` 时，最多能得到的展示方式数
`C_i`	这一组方案的单价
`x`	这一组的选择数量
`x * C_i`	这一组的总花费
`dp[j] * x`	选择这一组后的展示方式数

因为 C_i <= 199、K_i <= 10，总花费上界很小，所以可以直接对总花费做 DP。

做法是：

设 dp[j] 表示花费 j 时最多能得到多少展示方式数
初始 dp[0] = 1
依次处理每个英雄，把它看成一个分组
枚举这个英雄买 0 款或 2..K_i 款皮肤
用乘法更新展示方式数，并把结果截断到 M
最后从小到大找第一个 dp[j] >= M 的 j

DP 公式

设 $dp_j$ 表示花费 $j$ 时最多能得到多少展示方式数。初始：

dp_0=1

处理第 $i$ 个英雄时，若买 $x$ 款皮肤，花费为 $xC_i$ ，展示方式数乘上 $x$ ，则：

new_{j+xC_i}=\max(new_{j+xC_i},\ dp_j\cdot x)

其中 $x=0$ 或 $2\leqslant x\leqslant K_i$ 。最终答案为：

\min\{j\mid dp_j\geqslant M\}

公式解释：每个英雄是一组，只能在这一组中选择买几款皮肤。花费增加 xC_i，展示方式数乘以 x；最后扫描最小花费，是因为题目要求达到至少 M 的最低成本。

代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#include <bits/stdc++.h>
using namespace std;

static long long clamp_mul(long long a, int b, long long limit) {
    __int128 v = (__int128)a * b;
    if (v > limit) {
        return limit;
    }
    return (long long)v;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long M;
    cin >> N >> M;

    vector<int> K(N), C(N);
    for (int i = 0; i < N; ++i) {
        cin >> K[i];
    }
    for (int i = 0; i < N; ++i) {
        cin >> C[i];
    }

    int limit = 0;
    for (int i = 0; i < N; ++i) {
        limit += K[i] * C[i];
    }

    vector<long long> dp(limit + 1, 0), ndp(limit + 1, 0);
    dp[0] = 1;

    for (int i = 0; i < N; ++i) {
        // 先保留“不买当前英雄”的情况。
        ndp = dp;

        for (int cost = 0; cost <= limit; ++cost) {
            if (dp[cost] == 0) {
                continue;
            }

            for (int x = 2; x <= K[i]; ++x) {
                int nc = cost + x * C[i];
                if (nc > limit) {
                    break;
                }
                // 选 x 款皮肤后，展示方式数乘上 x。
                ndp[nc] = max(ndp[nc], clamp_mul(dp[cost], x, M));
            }
        }

        dp.swap(ndp);
    }

    for (int cost = 0; cost <= limit; ++cost) {
        if (dp[cost] >= M) {
            cout << cost << '\n';
            return 0;
        }
    }

    return 0;
}

复杂度

时间复杂度： $O(N * S * 10)$ ，其中 S 是总花费上界
空间复杂度： $O(S)$

由于 C_i <= 199，K_i <= 10，总花费上界仍然很小，所以这个 DP 是可行的。

总结

这题的本质是“分组背包 + 乘法收益”。

把每个英雄的皮肤数当成分组方案，按总花费做 DP，记录能得到的最大展示方式数，就能直接求出最小花费。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析