算法逻辑说明
- 使用 动态规划:
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)
}