题解 | 购物单

package main

import (
	"fmt"
)

// 定义物品结构体
type Item struct {
	price int // 价格 (已 /10)
	val   int // 满意度 (原价格 * 重要度)
}

func main() {
	// 1. 读取输入
	var n, m int
	fmt.Scan(&n, &m)

	// 优化：价格都是10的倍数，把钱都除以10，减小数组空间
	n /= 10

	// 2. 数据预处理：归类主件和附件
	// mainItems 存储主件，accessories 存储对应主件的附件列表
	// 题目中物品编号从1开始，我们这里用 map 或者数组索引对应
	// 为了方便，用数组，索引 1~m
	
	// goods[i][0] 存主件
	// goods[i][1] 存附件1
	// goods[i][2] 存附件2
	goods := make([][3]*Item, m+1)

	for i := 1; i <= m; i++ {
		var v, p, q int
		fmt.Scan(&v, &p, &q)
		
		vReal := v / 10     // 真正的花费（优化后）
		satisfaction := v * p // 满意度 = 价格 * 重要度

		item := &Item{price: vReal, val: satisfaction}

		if q == 0 {
			// 是主件
			goods[i][0] = item
		} else {
			// 是附件，q 是它所属的主件ID
			if goods[q][1] == nil {
				goods[q][1] = item
			} else {
				goods[q][2] = item
			}
		}
	}

	// 3. 动态规划
	// dp[j] 表示预算为 j 时的最大满意度
	dp := make([]int, n+1)

	for i := 1; i <= m; i++ {
		// 只处理主件，遇到主件时，顺便考察它的附件组合
		// 如果 goods[i][0] 是 nil，说明这个编号 i 可能是个附件（已经被上面的 q 处理过了），或者不存在
		if goods[i][0] == nil {
			continue
		}

		mainItem := goods[i][0]
		acc1 := goods[i][1]
		acc2 := goods[i][2]

		// 0/1 背包倒序遍历
		for j := n; j >= 0; j-- {
			// 临时变量，用于比较不同组合
			// 基础情况：必须买得起主件
			if j >= mainItem.price {
				// 1. 只买主件
				v1 := mainItem.price
				w1 := mainItem.val
				dp[j] = max(dp[j], dp[j-v1]+w1)

				// 2. 主件 + 附件1
				if acc1 != nil {
					v2 := v1 + acc1.price
					w2 := w1 + acc1.val
					if j >= v2 {
						dp[j] = max(dp[j], dp[j-v2]+w2)
					}
				}

				// 3. 主件 + 附件2
				if acc2 != nil {
					v3 := v1 + acc2.price
					w3 := w1 + acc2.val
					if j >= v3 {
						dp[j] = max(dp[j], dp[j-v3]+w3)
					}
				}

				// 4. 主件 + 附件1 + 附件2
				if acc1 != nil && acc2 != nil {
					v4 := v1 + acc1.price + acc2.price
					w4 := w1 + acc1.val + acc2.val
					if j >= v4 {
						dp[j] = max(dp[j], dp[j-v4]+w4)
					}
				}
			}
		}
	}

	fmt.Println(dp[n])
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}