英雄联盟

题意

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

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

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

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

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

思路

一句话本质：分组背包 + 乘法收益。每个英雄是一组，选 $0$ 或 $2 \sim K_i$ 款皮肤，总花费下最大化展示方式数的乘积，求达到 $M$ 的最小花费。

先看最直接的暴力：

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
28import sys

data = list(map(int, sys.stdin.buffer.read().split()))
N, M = data[0], data[1]
K = data[2:2 + N]
C = data[2 + N:2 + N + N]

limit = sum(K[i] * C[i] for i in range(N))

best = limit + 1

def dfs(i, cost, ways):
    global best
    if ways >= M:
        best = min(best, cost)
        return
    if i == N:
        return
    dfs(i + 1, cost, ways)
    for x in range(2, K[i] + 1):
        nc = cost + x * C[i]
        nw = ways * x
        if nw > M:
            nw = M
        dfs(i + 1, nc, nw)

dfs(0, 0, 1)
print(best)

brute.py 对每个英雄枚举买 $0$ 或 $2 \sim K_i$ 款，递归统计总花费和展示方式数乘积。 $N$ 最大约 $10$ ，但 $K_i$ 最多 $10$ ，组合搜索仍然很慢。

暴力里的决策有什么浪费？

注意 $x=1$ （买一款皮肤）展示方式数乘 $1$ ——不变，但花费增加了 $C_i$ 。这种方案严格劣于不买（ $x=0$ ，花费 $0$ ，展示方式不变）。所以每个英雄真正要枚举的只有 $0$ 和 $2 \sim K_i$ 。

展示方式数是乘法累积的，怎么放进 DP？

普通背包累加价值，这里累乘。但本质一样——每选一个英雄的方案，就把"状态值"（展示方式数）乘以 $x$ 。设 $dp_{cost}$ 表示花费 $cost$ 元时能达到的最大展示方式数。

怎么处理乘法溢出？

展示方式数可能巨大（每个英雄最多 $10$ 款皮肤， $N$ 个英雄的乘积），但只要 $\geqslant M$ 就够了。每次乘法结果和 $M$ 取 $\min$ ，截断后状态值不超过 $M$ 。

转移怎么做？

对第 $i$ 个英雄，枚举买 $x$ 款（ $x=0$ 或 $2 \leqslant x \leqslant K_i$ ）：

花费增加 $x \cdot C_i$
展示方式数 $= dp_{cost} \cdot x$ （截断到 $M$ ）

用备份数组 $ndp$ 做转移，避免同一英雄的方案互相影响。最终从小到大找第一个 $dp_{cost} \geqslant M$ 的 $cost$ 。

代码

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#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int N;
ll M;
int K[105], C[105];       // K[i] 上限展示量, C[i] 皮肤单价

// 乘法防溢出，超过 limit 就截断为 limit。
ll clamp_mul(ll a, int b, ll limit) {
    __int128 v = (__int128)a * b;
    if (v > limit) return limit;
    return (ll)v;
}

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

    cin >> N >> M;
    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];            // 花费的上限
    }

    // dp[cost] 表示花费 cost 元能达到的最大展示数量。
    vector<ll> dp(limit + 1, 0);
    dp[0] = 1;

    for (int i = 0; i < N; i++) {
        vector<ll> ndp = dp;
        for (int cost = 0; cost <= limit; cost++) {
            if (dp[cost] == 0) continue;
            // 在当前英雄上买 x 份皮肤（x ≥ 2）
            for (int x = 2; x <= K[i]; x++) {
                int nc = cost + x * C[i];
                if (nc > limit) break;
                ndp[nc] = max(ndp[nc], clamp_mul(dp[cost], x, M));
            }
        }
        dp.swap(ndp);
    }

    // 找到最小的花费使展示数量 ≥ M。
    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，记录能得到的最大展示方式数，就能直接求出最小花费。

一图流解析

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

目录

题意

思路

代码

复杂度

总结

一图流解析