小红的双生英雄

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define MAX(x,y) ((x) > (y)) ? (x) : (y)

typedef struct actor_info {
    int cost;
    int power;
    int is_pair;
} ActorInfo;

typedef struct pair_actor {
    int x;
    int y;
    int x_power;
    int y_power;
    int x_cost;
    int y_cost;
    int pair_cost;
    uint64_t pair_power;
} PairActor;

int main() {
    int actor_cnt = 0;
    int max_cost = 0;
    int pair_cnt = 0;
    scanf("%d %d %d", &actor_cnt, &max_cost, &pair_cnt);

    ActorInfo info[actor_cnt + 1];
    memset(info, 0, sizeof(info));
    for (int i = 1; i <= actor_cnt; i++) {
        scanf("%d %d", &info[i].cost, &info[i].power);
    }

    PairActor pair[pair_cnt];
    memset(pair, 0, sizeof(pair));
    for (int i = 0; i < pair_cnt; i++) {
        scanf("%d %d %ld", &pair[i].x, &pair[i].y, &pair[i].pair_power);

        info[pair[i].x].is_pair = 1;
        info[pair[i].y].is_pair = 1;

        pair[i].x_power = info[pair[i].x].power;
        pair[i].y_power = info[pair[i].y].power;
        pair[i].x_cost = info[pair[i].x].cost;
        pair[i].y_cost = info[pair[i].y].cost;
        pair[i].pair_cost = pair[i].x_cost + pair[i].y_cost;
        pair[i].pair_power += info[pair[i].x].power + info[pair[i].y].power;
    }


    uint64_t dp[5][1001] = {0};
    for (int i = 1; i <= actor_cnt; i++) {
        // 跳过双生英雄
        if (info[i].is_pair) {
            continue;
        }
        for (int j = 4; j > 0; j--) {
            for (int k = max_cost; k >= info[i].cost; k--) {
                // 两种情况最大值
                // 不选i英雄：dp[j][k]
                // 选i英雄：dp[j - 1][k - info[i].cost] + info[i].power
                dp[j][k] = MAX(dp[j][k], dp[j - 1][k - info[i].cost] + info[i].power);
            }
        }
    }


    for (int i = 0; i < pair_cnt; i++) {
        for (int j = 4; j > 0; j--) {
            for (int k = max_cost; k > 0; k--) {
                // 4种情况最大值
                // 不选：dp[j][k]
                // 选 x y：dp[j - 2][k - pair[i].pair_cost] + pair[i].pair_power
                // 选x：dp[j - 1][k - pair[i].x_cost] + pair[i].x_power
                // 选y：dp[j - 1][k - pair[i].y_cost] + pair[i].y_power
                uint64_t best_building = dp[j][k];
                if (k > pair[i].pair_cost && j >= 2) {
                    best_building = MAX(best_building, dp[j - 2][k - pair[i].pair_cost] + pair[i].pair_power);
                }
                if (k > pair[i].x_cost) {
                    best_building = MAX(best_building, dp[j - 1][k - pair[i].x_cost] + pair[i].x_power);
                }
                if (k > pair[i].y_cost) {
                    best_building = MAX(best_building, dp[j - 1][k - pair[i].y_cost] + pair[i].y_power);
                }
                dp[j][k] = best_building;
            }
        }

    }

    uint64_t max_power = 0;
    for (int i = 1; i <= 4; i++) {
        max_power = max_power > dp[i][max_cost] ? max_power : dp[i][max_cost];
    }
    printf("%ld\n", max_power);
}