题解 | 小红的双生英雄

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

#undef DEBUG
#ifdef DEBUG
#define debug(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#define debug(fmt, ...)
#endif

long long DP[2][6][1000];

typedef struct hero {
    long long cost;
    long long power;
    int twin;
    long long bonus;
} hero_t;


int main() {
    int n, C, m;
    int k,j;
    long long a, b;
    scanf("%d %d %d", &n, &C, &m);
    debug("n = %d, C = %d, m = %d\n", n, C, m);
    hero_t* heros = (hero_t*)malloc(sizeof(hero_t) * (n + 1));
    int i;
    for (i = 1; i <= n; i++) {
        scanf("%lld %lld", &heros[i].cost, &heros[i].power);
        heros[i].twin = heros[i].bonus = 0;
    }
    int h1, h2;
    long long bonus;
    for (i = 0; i < m; i++) {
        scanf("%d %d %lld", &h1, &h2, &bonus);
        heros[h1].twin = h2;
        heros[h2].twin = h1;
        heros[h1].bonus = bonus;
        heros[h2].bonus = bonus;
    }
    for(i = 1; i <= n; i++)
        debug("cost[%lld] power[%lld] twin[%d] bonus[%lld]\n", \
            heros[i].cost, heros[i].power, heros[i].twin, heros[i].bonus);
    memset(DP, 0 ,sizeof(DP));

    for(i = 1; i <= n; i++) {
        int sel_n = i & 1;
        int sel_l = sel_n ^ 1;
        int twin_i = heros[i].twin;

        for(k = 0; k <= 4; k++) {
            for(j = 0; j <= C; j++) {
                DP[sel_n][k][j] = DP[sel_l][k][j];
            }
        }

        if(twin_i != 0 && twin_i < i) continue;

        for(k = 1; k <= 4; k++) {
            for(j = heros[i].cost; j <= C; j++) {
                long long previous = DP[sel_l][k-1][j - heros[i].cost] + heros[i].power;
                if(previous > DP[sel_n][k][j]) {
                    DP[sel_n][k][j] = previous;
                }
            }
        }
        
        if(twin_i == 0) continue;

        for(k = 1; k <= 4; k++) {
            for(j = heros[twin_i].cost; j <= C; j++) {
                long long previous = DP[sel_l][k-1][j - heros[twin_i].cost] + heros[twin_i].power;
                if(previous > DP[sel_n][k][j]) {
                    DP[sel_n][k][j] = previous;
                }
            }
        }

        long long total_cost = heros[i].cost + heros[twin_i].cost;
        for(k = 2; k <= 4; k++) {
            for(j = total_cost; j <= C; j++) {
                long long previous = DP[sel_l][k-2][j - total_cost] + \
                            heros[i].power + heros[twin_i].power + heros[i].bonus;
                if(previous > DP[sel_n][k][j]) {
                    DP[sel_n][k][j] = previous;
                }
            }
        }

    }

    long long ans = 0;
    int sel_n = n & 1;
    for(k = 0; k <= 4; k++) {
        if(DP[sel_n][k][C] > ans) {
            ans = DP[sel_n][k][C];
        }
    }

    printf("%lld\n",ans);
    return 0;
}