洛谷 P5365 [SNOI2017] 英雄联盟

// P5365 [SNOI2017] 英雄联盟 —— ★ 这一版就能 AC
//
// 题意：N 个英雄，第 i 个有 K[i] 款皮肤、每款 C[i] Q 币。
//       给第 i 个英雄买 k 款，展示策略数就乘上 k（买 0 款的英雄不参与展示）。
//       要让**策略数 ≥ M**，问最少花多少钱。
//
// ★ 关键的一步（一）：**把「花费」当容量、「策略数」当价值** ——
//   这是一个**分组背包**：每个英雄是一组，组内选「买几款」（0 .. K[i]），最多选一个。
//     f[j] = 花不超过 j 元时，能达到的**最大策略数**
//     f[j] = max(f[j], f[j − k·C[i]] × k)      k = 2 .. K[i]
//   答案 = 最小的 j 使 f[j] ≥ M。
//
// ★ 关键的一步（二）：**k = 1 永远不用考虑** —— 买 1 款和买 0 款对乘积都是 ×1，
//   而买 1 款要多花 C[i]。⇒ 内层从 k = 2 起。
//   （反过来，**强制每个英雄至少买 1 款**是一个真实的错法，见解析页第 ③ 步。）
//
// ★★★ 关键的一步（三）：**乘积必须截断**。
//   N 顶格 121、每个英雄 10 款 ⇒ 策略数最大 10^121，`long long` 装不下十分之一。
//   而我们只关心「有没有到 M」⇒ 把每次乘出来的值**和 M 取 min** 就行。
//   ⇒ 不截断会溢出成负数，答案当场错（解析页第 ④ 步）。
//
// ⚠ 容量上界是算出来的：Σ K[i]·C[i] ≤ 121 × 10 × 199 = 240 790。
// ⚠ M ≤ 10^17 ⇒ 读 M 必须用 long long。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n;
    ll M;
    if (!(cin >> n >> M)) return 0;
    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 cap = 0;
    for (int i = 0; i < n; i++) cap += K[i] * C[i];      // ★ 容量上界：全买满

    vector<ll> f(cap + 1, 1);                           // 一款都不买 ⇒ 策略数 1
    for (int i = 0; i < n; i++)
        for (int j = cap; j >= 0; j--)                  // 倒序：这一组只选一次
            for (int k = 2; k <= K[i]; k++) {           // ★ k = 1 和 k = 0 等价，跳过
                int cost = k * C[i];
                if (cost > j) break;
                ll v = f[j - cost] * k;
                if (v > M) v = M;                       // ★★★ 截断，否则 10^121 会溢出
                f[j] = max(f[j], v);
            }

    for (int j = 0; j <= cap; j++)
        if (f[j] >= M) { cout << j << "\n"; return 0; }
    cout << cap << "\n";                                // 题面保证有解，走不到这儿
    return 0;
}