题解 | 小红的双生英雄

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++ {
		// 由于每次只依赖前一个状态，所以可以用奇偶位实现滚动，将空间复杂度从 O(n*k*c) 降到 O(k*c)。
		cur := i & 1
		prev := cur ^ 1

		// 拷贝上一行状态，这一步代表：“不选第 i 个英雄”的情况。
		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)
}