题解 | 小红的双生英雄

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

struct Hero {
    int cost;
    long long power;
};

struct Twin {
    int u, v;
    long long bonus;
};

int main() {
    int n, C, m;
    cin >> n >> C >> m;
    vector<Hero> heroes(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> heroes[i].cost >> heroes[i].power;
    }

    vector<Twin> twins(m);
    for (int i = 0; i < m; i++) {
        cin >> twins[i].u >> twins[i].v >> twins[i].bonus;
    }

    long long dp[5][1001] = {0}; // dp[p][j] 表示选择 p 个英雄且总 cost 不超过 j 时的最大战斗力
    for (int i = 1; i <= n; i++) {
        for (int p = 4; p > 0; p--) {
            for (int j = C; j >= heroes[i].cost; j--) {
                dp[p][j] = max(dp[p][j], dp[p - 1][j - heroes[i].cost] + heroes[i].power);
            }
        }
    }

    // 处理双生英雄关系
    for (const auto& twin : twins) {
        int u = twin.u, v = twin.v;
        long long bonus = twin.bonus;
        for (int p = 4; p >= 2; p--) {
            for (int j = C; j >= heroes[u].cost + heroes[v].cost; j--) {
                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;
}