题解 | 小红的双生英雄

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

int main() {
    int n, C, m;
    cin >> n >> C >> m;
    int costs[1001] = {};
    long long fightings[1001] = {};
    int connections[1001] = {};
    int unionfights[1001] = {};
    for (int i = 1; i <= n; i++) {
        cin >> costs[i] >> fightings[i];
    }
    int u, v, w;
    for (int i = 1; i <= m ; i++) {
        cin >> u >> v >> w;
        if(u > v){
            swap(u, v);
        }
        connections[u] = v;
        unionfights[u] = w;
    }

    long long dp[5][1001] = {};
    for (int i = 1; i <= n; i++) {
        int k = connections[i];
        for (int p = 4; p > 0; p--) {
            if (k == 0) {
                for (int j = C; j >= costs[i]; j--) {
                    dp[p][j] = max(dp[p][j], dp[p - 1][j - costs[i]] + fightings[i]);
                }
            } else if (k > i) {
                int low_bound = min(costs[i], costs[k]);
                for (int j = C; j >= low_bound; j--) {
                    if (j - costs[i] >= 0) {
                        dp[p][j] = max(dp[p][j], dp[p - 1][j - costs[i]] + fightings[i]);
                    }
                    if (j - costs[k] >= 0) {
                        dp[p][j] = max(dp[p][j], dp[p - 1][j - costs[k]] + fightings[k]);
                    }
                    if (j - costs[i] - costs[k] >= 0 && p >= 2) {
                        dp[p][j] = max(dp[p][j], dp[p - 2][j - costs[i] - costs[k]] + fightings[i] + fightings[k] +
                                    unionfights[i]);
                    }
                }
            }
        }
    }
    long long ans = 0;
    for(int i = 0; i < 5; i++) {
        if(ans < dp[i][C]) {
            ans = dp[i][C];
        }
    }
    cout << ans;
}
// 64 位输出请用 printf("%lld")