Upgrading Technology - 题解

标签与难度

标签: 动态规划, 前缀和, 最优解, 迭代枚举 难度: 1900

题目大意喵~

你好呀，指挥官！Rowlet 酱在宝可梦世界里遇到了一个关于科技树升级的难题，需要我们帮忙呢，喵~

游戏里有 $n$ 种科技，每种科技都可以从 0 级升到 $m$ 级。

• 把第 $i$ 种科技从 $j-1$ 级升到 $j$ 级，需要花费 $c_{ij}$ 的宝可元。这个花费可能是负数，也就是说升级有时还能赚钱哦！
• 更棒的是，如果所有的 $n$ 种科技都达到了至少 $j$ 级，我们就能获得一笔 $d_j$ 的额外奖励！当然，这个奖励也可能是负的啦。

我们的目标是，找到一个最佳的升级策略，让最终获得的宝可元最多！当然，我们也可以选择什么都不升级，这样收益就是 0。

解题思路分析

这道题看起来有点复杂，因为每种科技的最终等级 $l_i$ 都会相互影响，特别是那个集体奖励 $d_j$ 是由所有科技的最低等级决定的，喵~

直接去想每种科技升到多少级，组合太多了，肯定会头晕的。所以，我们需要找到一个关键点来简化问题！这个关键点就是——所有科技最终达到的最低公共等级！

让我来带你一步步拆解这个问题吧，呐~

核心思想：枚举最低公共等级

我们可以换个角度思考：如果我们最终的升级策略，使得所有科技的最低等级是 $k$（$0 \le k \le m$），那么我们能获得的最大利润是多少呢？

只要我们能算出对于每一个固定的最低等级 $k$，能获得的最大利润，再从所有可能的 $k$（从 0 到 $m$）中取一个最大值，不就是最终答案了吗？喵~

好，现在我们假设，我们定下了一个小目标：所有科技的等级都必须大于等于 $k$。

1. 获得奖励：既然所有科技都达到了 $k$ 级，我们就能稳稳地拿到从 1 级到 $k$ 级的所有奖励。总奖励就是 $\sum_{j=1}^{k} d_j$。

2. 计算花费：为了实现这个目标，每一种科技 $i$ 都必须至少升到 $k$ 级。但是，为了让总利润最大化（也就是总花费最小化），我们是不是应该把每一种科技都只升到 $k$ 级呢？不一定哦！因为有些科技从 $k$ 级继续往上升，可能会因为 $c_{ij}$ 是负数而带来更多收益。

所以，对于每一种科技 $i$，在满足等级不低于 $k$ 的前提下，我们应该将它升级到一个最优的等级 $l_i$ ($l_i \ge k$)，使得升级到 $l_i$ 的总花费 $\sum_{j=1}^{l_i} c_{ij}$ 是所有可能选择中（$l_i \ge k$）最小的。

数学化表达

让我们把思路变得更清晰一些，喵~

• 令 $C_{i,j} = \sum_{p=1}^{j} c_{ip}$ 表示将第 $i$ 种科技从 0 级升到 $j$ 级的累计花费。$C_{i,0}=0$。
• 令 $D_k = \sum_{j=1}^{k} d_j$ 表示最低公共等级达到 $k$ 时能获得的累计奖励。$D_0=0$。

当我们固定最低公共等级为 $k$ 时：

• 我们获得的累计奖励是 $D_k$。
• 对于第 $i$ 种科技，我们必须将它升级到某个等级 $l_i \ge k$。为了让花费最小，我们应该选择那个使得 $C_{i,l_i}$ 最小的 $l_i$。所以，第 $i$ 种科技的最小花费是 $\min_{l=k}^{m} C_{i,l}$。
• 所有科技的总花费就是 $\sum_{i=1}^{n} (\min_{l=k}^{m} C_{i,l})$。

所以，当最低公共等级为 $k$ 时，我们的最大利润是：

$$\text{Profit}(k) = D_k - \sum_{i=1}^{n} \left( \min_{l=k}^{m} C_{i,l} \right)$$

最终的答案就是所有可能中的最大值：

$$\text{MaxProfit} = \max_{k=0}^{m} \left( \text{Profit}(k) \right)$$

当然，如果算出来的最大利润是负数，我们应该选择什么都不做，所以最终答案还要和 0 取一个最大值。

如何高效计算？

现在公式有了，直接计算的话效率怎么样呢？ 我们需要快速求出 $C_{i,j}$, $D_k$ 和 $\min_{l=k}^{m} C_{i,l}$。

1. 累计花费 $C_{i,j}$ 和累计奖励 $D_k$：这不就是经典的前缀和嘛！

   • cumulative_cost[i][j] = cumulative_cost[i][j-1] + c[i][j]
   • cumulative_bonus[k] = cumulative_bonus[k-1] + d[k] 这部分计算的时间复杂度是 $O(nm)$。

2. 区间最小花费 $\min_{l=k}^{m} C_{i,l}$：对于固定的科技 $i$，我们需要知道从 $k$ 到 $m$ 级中，哪个累计花费最小。这可以用后缀最小值来解决！

   • 我们定义 min_future_cost[i][k] 表示 $\min_{l=k}^{m} C_{i,l}$。
   • 可以从后往前递推：min_future_cost[i][k] = min(cumulative_cost[i][k], min_future_cost[i][k+1])。
   • min_future_cost[i][m+1] 可以初始化为一个非常大的数。 这部分计算的时间复杂度也是 $O(nm)$。

万事俱备！我们只需要预处理出这些值，然后就可以愉快地枚举 $k$ 从 0 到 $m$，套用公式计算并找到最大值啦，喵~

代码实现

下面是我根据上面的思路，精心为你准备的代码哦！注释写得很详细，希望能帮到你，喵~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

// 使用 long long 来防止溢出，毕竟钱的事情不能马虎，喵~
using ll = long long;

const ll INF = 1e18; // 一个足够大的数，代表正无穷

void solve() {
    int n, m;
    cin >> n >> m;

    vector<vector<ll>> costs(n, vector<ll>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> costs[i][j];
        }
    }

    vector<ll> bonuses(m);
    for (int i = 0; i < m; ++i) {
        cin >> bonuses[i];
    }

    // --- 步骤1: 预处理累计花费 (前缀和) ---
    // cumulative_costs[i][j] 表示将科技 i 升到 j 级的总花费
    vector<vector<ll>> cumulative_costs(n, vector<ll>(m + 1, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cumulative_costs[i][j + 1] = cumulative_costs[i][j] + costs[i][j];
        }
    }

    // --- 步骤2: 预处理累计奖励 (前缀和) ---
    // cumulative_bonuses[j] 表示最低公共等级达到 j 时能拿到的总奖励
    vector<ll> cumulative_bonuses(m + 1, 0);
    for (int i = 0; i < m; ++i) {
        cumulative_bonuses[i + 1] = cumulative_bonuses[i] + bonuses[i];
    }

    // --- 步骤3: 预处理未来最小花费 (后缀最小值) ---
    // min_future_costs[i][k] 表示对于科技 i，在等级 >= k 的所有选择中，最小的累计花费是多少
    vector<vector<ll>> min_future_costs(n, vector<ll>(m + 2, INF));
    for (int i = 0; i < n; ++i) {
        for (int k = m; k >= 0; --k) {
            min_future_costs[i][k] = min(cumulative_costs[i][k], min_future_costs[i][k + 1]);
        }
    }

    // --- 步骤4: 枚举最低公共等级 k，计算并找出最大利润 ---
    ll max_profit = 0; // 初始最大利润为0，因为我们可以什么都不做

    for (int k = 0; k <= m; ++k) {
        // 计算当最低公共等级为 k 时，所有科技的总花费
        ll total_min_cost_at_k = 0;
        for (int i = 0; i < n; ++i) {
            total_min_cost_at_k += min_future_costs[i][k];
        }

        // 当前策略的利润 = 累计奖励 - 总花费
        ll current_profit = cumulative_bonuses[k] - total_min_cost_at_k;
        
        // 更新全局最大利润
        max_profit = max(max_profit, current_profit);
    }

    cout << max_profit << "\n";
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        cout << "Case #" << i << ": ";
        solve();
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O(N \times M)$

  • 预处理累计花费和累计奖励需要 $O(N \times M)$。
  • 预处理未来最小花费（后缀最小值）需要 $O(N \times M)$。
  • 最后枚举最低公共等级 $k$ 的循环，内部对 $N$ 个科技求和，总共是 $O(N \times M)$。
  • 所以总的时间复杂度就是 $O(N \times M)$，对于 $N, M \le 1000$ 来说是完全可以接受的，喵~

• 空间复杂度: $O(N \times M)$

  • 我们主要使用了 cumulative_costs 和 min_future_costs 两个二维数组来存储中间结果，它们的大小都是 $N \times M$ 级别的。所以空间复杂度是 $O(N \times M)$。

知识点总结

这道题虽然看起来有点绕，但只要抓住了核心，就能把它变成一个我们熟悉的问题！

1. 问题分解: 面对一个复杂的最优化问题，尝试固定一个关键变量（本题中是“最低公共等级”），将问题分解成一系列更简单的子问题，然后合并子问题的解。这是一种非常重要的解题思想！
2. 前缀和/后缀和: 这是处理区间/累积问题的神器！通过预处理，可以把多次查询的复杂度从线性降到常数。在这里我们用它来快速计算累计花费和奖励。
3. 后缀最小值/最大值: 和前缀和类似，这也是一种预处理技巧。当我们关心一个点之后所有位置的最值时，用它就对啦。

希望这篇题解能帮助你理解这道题的奥秘！要继续加油哦，指挥官！喵~