小红的双生英雄

#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);
}

算法逻辑说明

• 使用 动态规划：dp[i][k][j] 表示前 i 个英雄中选了 k 个，总 cost 为 j 时的最大战斗力。
• 使用滚动数组优化空间（只保留两层）。
• 每个英雄最多属于一个“双生对”，处理时避免重复。
• 对于双生英雄 (u, v)，只有当两者都被选时，才加上额外战斗力 w。
• 遍历每个英雄，分情况更新 DP：
• 只选当前英雄
• 只选其配对英雄（如果前面已处理）
• 同时选当前和配对英雄（触发双生加成）

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type Hero struct {
	cost, v, tp, fnv int64
}

func main() {
	reader := bufio.NewReader(os.Stdin)

	// 读取第一行 n, C, m
	line, _ := reader.ReadString('\n')
	parts := strings.Fields(line)
	n, _ := strconv.Atoi(parts[0])
	costLimit, _ := strconv.Atoi(parts[1])
	m, _ := strconv.Atoi(parts[2])

	// 初始化英雄数组
	heroes := make([]Hero, n+1) // 1-indexed

	// 读取 n 个英雄的 cost 和战斗力
	for i := 1; i <= n; i++ {
		line, _ = reader.ReadString('\n')
		parts = strings.Fields(line)
		a, _ := strconv.ParseInt(parts[0], 10, 64)
		b, _ := strconv.ParseInt(parts[1], 10, 64)
		heroes[i] = Hero{cost: a, v: b}
	}

	// 读取 m 对双生英雄
	for i := 0; i < m; i++ {
		line, _ = reader.ReadString('\n')
		parts = strings.Fields(line)
		u, _ := strconv.Atoi(parts[0])
		v, _ := strconv.Atoi(parts[1])
		w, _ := strconv.ParseInt(parts[2], 10, 64)

		heroes[u].tp = int64(v)
		heroes[v].tp = int64(u)
		heroes[u].fnv = w
		heroes[v].fnv = w
	}

	// DP 数组：dp[滚动][k个英雄][总cost] -> 最大战斗力
	// dp[i&1][k][j] 滚动使用
	const MAX_K = 5
	const MAX_COST = 1001
	var dp [2][MAX_K][MAX_COST]int64

	// 初始化 dp 为 0（Go 默认为 0，安全）
	// 使用滚动数组：cur 和 prev
	for i := 1; i <= n; i++ {
		cur := i & 1
		prev := cur ^ 1

		// 拷贝上一行状态
		for k := 0; k < MAX_K; k++ {
			for j := 0; j <= costLimit; j++ {
				dp[cur][k][j] = dp[prev][k][j]
			}
		}

		tp := heroes[i].tp
		if tp != 0 && int64(tp) < int64(i) {
			// 避免重复处理双生对，只在较大的索引处理
			continue
		}

		// 情况1：只选当前英雄 i
		for k := 1; k < MAX_K; k++ {
			for j := int(heroes[i].cost); j <= costLimit; j++ {
				prevVal := dp[prev][k-1][j-int(heroes[i].cost)]
				if prevVal+heroes[i].v > dp[cur][k][j] {
					dp[cur][k][j] = prevVal + heroes[i].v
				}
			}
		}

		// 如果没有配对英雄，跳过后续双生逻辑
		if tp == 0 {
			continue
		}

		// 情况2：只选配对英雄 tp
		for k := 1; k < MAX_K; k++ {
			tpCost := int(heroes[tp].cost)
			if tpCost > costLimit {
				continue
			}
			for j := tpCost; j <= costLimit; j++ {
				prevVal := dp[prev][k-1][j-tpCost]
				if prevVal+heroes[tp].v > dp[cur][k][j] {
					dp[cur][k][j] = prevVal + heroes[tp].v
				}
			}
		}

		// 情况3：同时选 i 和 tp，触发双生加成
		totalCost := int(heroes[i].cost + heroes[tp].cost)
		if totalCost <= costLimit {
			for k := 2; k < MAX_K; k++ {
				for j := totalCost; j <= costLimit; j++ {
					prevVal := dp[prev][k-2][j-totalCost]
					totalV := prevVal + heroes[i].v + heroes[tp].v + heroes[i].fnv
					if totalV > dp[cur][k][j] {
						dp[cur][k][j] = totalV
					}
				}
			}
		}
	}

	// 在所有选 0~4 个英雄、总 cost <= costLimit 的状态中找最大值
	ans := int64(0)
	final := n & 1
	for k := 0; k < MAX_K; k++ {
		if dp[final][k][costLimit] > ans {
			ans = dp[final][k][costLimit]
		}
	}

	fmt.Println(ans)
}

好几个代码应该是有问题的

都是直接单人dp一遍  双人dp一遍  

没有考虑到使用双生时 其中的英雄已经使用过的情况

2 40 1
5 10
5 10
1 2 10

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define C getchar()-48
inline ll read(){
    ll s=0,r=1;
    char c=C;
    for(;c<0||c>9;c=C) if(c==-3) r=-1;
    for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c;
    return s*r;
}
#define rep(i,sti,edi) for(int i=sti;i<=edi;i++)
const int N=1e3+10;
int n,cost,m;
ll dp[3][6][N];
struct xin{
    ll cost=0,v=0,tp=0,fnv=0;
}a[N];
int main(){
    n=read(),cost=read(),m=read();
    rep(i,1,n) a[i].cost=read(),a[i].v=read();
    rep(i,1,m){
        int x=read(),y=read();ll v=read();
        a[x].tp=y;a[y].tp=x;
        a[x].fnv=a[y].fnv=v;
    }
    rep(i,1,n){
        int dqkd=i&1;int qmkd=dqkd^1;
        int tpi=a[i].tp;
        rep(k,0,4) rep(j,0,cost) 
            dp[dqkd][k][j]=dp[qmkd][k][j];
        if(tpi&&tpi<i) continue;
        rep(k,1,4) rep(j,a[i].cost,cost) 
            dp[dqkd][k][j]=max(dp[dqkd][k][j],dp[qmkd][k-1][j-a[i].cost]+a[i].v);
        if(!tpi) continue;
        rep(k,1,4) rep(j,a[tpi].cost,cost) 
            dp[dqkd][k][j]=max(dp[dqkd][k][j],dp[qmkd][k-1][j-a[tpi].cost]+a[tpi].v);
        rep(k,2,4) rep(j,a[i].cost+a[tpi].cost,cost) 
            dp[dqkd][k][j]=max(dp[dqkd][k][j],dp[qmkd][k-2][j-a[i].cost-a[tpi].cost]+a[i].v+a[tpi].v+a[i].fnv);      
    }
    ll ans=0;
    rep(k,0,4) ans=max(ans,dp[n&1][k][cost]); 
    cout<<ans;
    return 0;
}

仿 HJ16 购物单 题写的解法，自测通过，但是提交不通过，求大佬帮忙看看。

n,Cost,m = map(int,input().split())

hero_data = {}

con_data = {}

for i in range(1,n+1):

    hero_data[i] = list(map(int,input().split()))

for i in range(1,m+1):

    u,v,w = list(map(int,input().split()))

    u,v = [u,v] if u > v else [v,u]

    con_data[u] = [v,w]

C,V = {},{}

for i in hero_data:

    if i not in con_data:

        C[i] = [0,0]

        V[i] = [0,0,0]

for i in hero_data:

    if i in con_data:

        C[con_data[i][0]][1] = hero_data[i][0]

        V[con_data[i][0]][1] = hero_data[i][1]

        V[con_data[i][0]][2] = con_data[i][1]

    else:

        C[i][0] = hero_data[i][0]

        V[i][0] = hero_data[i][1]

C,V = [C[key] for key in C],[V[key] for key in V]

dp = [[[0]*(Cost+1) for _ in range(len(C)+1)] for _ in range(5)]

for k in range(1,5):

    for i in range(1,len(C)+1):

        for j in range(1,Cost+1):

            dp[k][i][j] = dp[k][i-1][j]    # 不选i英雄

            if C[i-1][0] # 选i英雄

                dp[k][i][j] = max(dp[k][i][j],V[i-1][0]+dp[k-1][i-1][j-C[i-1][0]])

            if C[i-1][1] != 0 and C[i-1][1] # 选羁绊英雄

                dp[k][i][j] = max(dp[k][i][j],V[i-1][1]+dp[k-1][i-1][j-C[i-1][1]])

            if C[i-1][1] != 0 and C[i-1][0] + C[i-1][1] and k >= 2:   # 选两个英雄凑羁绊

                dp[k][i][j] = max(dp[k][i][j],V[i-1][0]+V[i-1][1]+V[i-1][2]+dp[k-2][i-1][j-C[i-1][0]-C[i-1][1]])

print(dp[-1][-1][-1])

n, C, m = map(int, input().split())
costs = [0] * (n + 1)
fightings = [0] * (n + 1)
connections = [0] * (n + 1)
unionfights = [0] * (n + 1)

for i in range(1, n + 1):
    costs[i], fightings[i] = map(int, input().split())

for _ in range(m):
    u, v, w = map(int, input().split())
    if u > v:
        u, v = v, u
    connections[u] = v
    unionfights[u] = w

dp = [[0] * (C + 1) for _ in range(5)]  # dp[p][j]: 用p个物品，容量为j时的最大战斗力

for i in range(1, n + 1):
    k = connections[i]
    for p in range(4, 0, -1):
        if k == 0:
            for j in range(C, costs[i] - 1, -1):
                dp[p][j] = max(dp[p][j], dp[p - 1][j - costs[i]] + fightings[i])
        elif k > i:
            low_bound = min(costs[i], costs[k])
            for j in range(C, low_bound - 1, -1):
                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 and p >= 2:
                    dp[p][j] = max(dp[p][j], dp[p - 2][j - costs[i] - costs[k]] +
                                   fightings[i] + fightings[k] + unionfights[i])

ans = max(dp[i][C] for i in range(5))
print(ans)