题解 | 小红的双生英雄

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 定义英雄结构体，存储每个英雄的 cost 和 power
struct Hero {
    int cost;
    long long power;
};

// 定义双生英雄关系结构体，存储双生英雄的索引和额外战斗力
struct Twin {
    int u, v;
    long long bonus;
};

int main() {
    int n, C, m; // 英雄数量、总 cost 限制、双生英雄对数
    cin >> n >> C >> m;
    vector<Hero> heroes(n + 1); // 存储所有英雄的信息
    for (int i = 1; i <= n; i++) {
        cin >> heroes[i].cost >> heroes[i].power; // 读取每个英雄的 cost 和 power
    }

    vector<Twin> twins(m); // 存储所有双生英雄关系
    for (int i = 0; i < m; i++) {
        cin >> twins[i].u >> twins[i].v >> twins[i].bonus; // 读取每对双生英雄的索引和额外战斗力
    }

    // 初始化动态规划数组，dp[p][j] 表示选择 p 个英雄且总 cost 不超过 j 时的最大战斗力
    long long dp[5][1001] = {0};
    // 遍历每个英雄，更新 dp 数组
    for (int i = 1; i <= n; i++) {
        // 从后往前更新，避免重复计算
        for (int p = 4; p > 0; p--) {
            // 从最大 cost 开始更新，确保每个状态只被更新一次
            for (int j = C; j >= heroes[i].cost; j--) {
                // 更新 dp 数组，选择当前英雄
                dp[p][j] = max(dp[p][j], dp[p - 1][j - heroes[i].cost] + heroes[i].power);
            }
        }
    }

    // 处理双生英雄关系，更新 dp 数组
    for (const auto& twin : twins) {
        int u = twin.u, v = twin.v; // 双生英雄的索引
        long long bonus = twin.bonus; // 双生英雄的额外战斗力
        // 从后往前更新，避免重复计算
        for (int p = 4; p >= 2; p--) {
            // 从最大 cost 开始更新，确保每个状态只被更新一次
            for (int j = C; j >= heroes[u].cost + heroes[v].cost; j--) {
                // 更新 dp 数组，选择两个双生英雄
                dp[p][j] = max(dp[p][j], dp[p - 2][j - heroes[u].cost - heroes[v].cost] + heroes[u].power + heroes[v].power + bonus);
            }
        }
    }

    // 找到最大战斗力
    long long ans = 0;
    for (int p = 0; p <= 4; p++) {
        ans = max(ans, dp[p][C]); // 遍历所有可能的英雄数量，找到最大战斗力
    }

    cout << ans << endl; // 输出结果
    return 0;
}