洛谷 P1853 [NWERC 2004] 投资的最大效益

// P1853 [NWERC 2004] 投资的最大效益 —— ★ 这一版就能 AC
//
// 题意：初始资产 s，投资 n 年，d 种债券；第 i 种投资额 a[i]、年息 b[i]，
//       **每种可以买任意多份**（钱够就行）。每年可以重新配置一次。求 n 年后的最大总资产。
//
// ★ 关键的一步（一）：**每一年就是一次完全背包** —— 容量是「当年的资产」，
//   价值是「年息」。而年与年之间只有一根线：`资产 += 这一年的最大利息`。
//   ⇒ 这就是题单说的「**DP 套在循环里**」。
//
// ★ 关键的一步（二）：**每年独立地把利息做到最大，就是全局最优。**
//   凭什么？「资产更多 ⇒ 今年能拿到的利息不会更少」（容量单调）——
//   所以今年多赚一分，明年的可行集只会更大。⇒ 不必在年之间做 DP。
//   （解析页第 ② 步用一个**不假设这件事**的全局暴力把它验了一遍。）
//
// ★★★ 关键的一步（三）：题面那句「**a 是 1000 的倍数**」是一张许可证 ——
//   把所有金额**除以 1000**，背包容量从 4.5 × 10^7 变成 4.5 × 10^4，规模缩 1000 倍。
//   不除的话是 1.8 × 10^10 次，必挂（解析页第 ③ 步量了）。

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

int main() {
    long long s;
    int n, d;
    if (!(cin >> s >> n >> d)) return 0;
    vector<int> a(d), b(d);
    for (int i = 0; i < d; i++) { cin >> a[i] >> b[i]; a[i] /= 1000; }   // ★ 除以 1000

    // 资产上界：每年最多涨 10%（利息 ≤ 投资额的 10% ≤ 资产的 10%）
    // ⇒ s ≤ 10^6 × 1.1^40 ≈ 4.53 × 10^7 ⇒ 除以 1000 之后 45260 格，开 50001 富余
    const int MAXC = 50001;
    vector<int> f(MAXC, 0);

    for (int year = 0; year < n; year++) {
        int cap = (int)(s / 1000);                    // 能动用的「千元」数
        if (cap >= MAXC) cap = MAXC - 1;
        fill(f.begin(), f.begin() + cap + 1, 0);
        for (int i = 0; i < d; i++)
            for (int j = a[i]; j <= cap; j++)         // ★ 正序 —— 每种债券可以买任意多份
                f[j] = max(f[j], f[j - a[i]] + b[i]);
        s += f[cap];                                  // 本金留着，利息滚进来
    }
    cout << s << "\n";
    return 0;
}

// P1853 错法二：容量一直用**初始资产**，不跟着涨
//
// 「每年跑一次完全背包」这句话记住了，可容量忘了更新 ——
// 于是第 2 年之后赚到的钱躺在账上，谁也没去投。
//
// ★ 说清楚它算了什么：它的答案**恒等于「n 年每年都赚初始资产能赚的那份利息」**，
//   也就是 `s + n × f(s)`。解析页第 ④ 步把这句话量成了 300 组逐组相等。
//   ⇒ 它是**线性增长**，而正解是**指数增长** —— 年数越多差得越离谱。

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

int main() {
    long long s;
    int n, d;
    if (!(cin >> s >> n >> d)) return 0;
    vector<int> a(d), b(d);
    for (int i = 0; i < d; i++) { cin >> a[i] >> b[i]; a[i] /= 1000; }

    const int MAXC = 50001;
    int cap = (int)(s / 1000);                         // ⚠ 只算了一次，之后再没更新
    if (cap >= MAXC) cap = MAXC - 1;
    vector<int> f(cap + 1, 0);
    for (int i = 0; i < d; i++)
        for (int j = a[i]; j <= cap; j++)
            f[j] = max(f[j], f[j - a[i]] + b[i]);

    for (int year = 0; year < n; year++) s += f[cap];
    cout << s << "\n";
    return 0;
}