题解 | #购物单#

package main

import (
	"fmt"
)

// 直接分成2个数组：主件数组和附件数组

type Product struct {
	Price int // 价格
	Sat   int // 满意度
	Index int // 索引
	Num   int // 编号，0主件，大于0副件
}

// 附件按照总体满意度排序
var attachProducts map[int][]Product
var memo [][]int

func main() {

	attachProducts = make(map[int][]Product, 0)
	mainProducts := make([]Product, 0)

	n, m := 0, 0
	_, _ = fmt.Scan(&n, &m)
	for i := 1; i <= m; i++ {
		v, p, q := 0, 0, 0
		_, _ = fmt.Scan(&v, &p, &q)

		if q == 0 {
			mainProducts = append(mainProducts, Product{
				Price: v,
				Sat:   p,
				Index: i,
			})
		} else {
			if _, ok := attachProducts[q]; !ok {
				attachProducts[q] = make([]Product, 0)
			}
			attachProducts[q] = append(attachProducts[q], Product{
				Price: v,
				Sat:   p,
				Index: i,
			})
		}
	}

	memo = make([][]int, n+1)
	for i := 0; i < len(memo); i++ {
		tmp := make([]int, 0)
		for j := 0; j <= len(mainProducts); j++ {
			tmp = append(tmp, -666)
		}
		memo[i] = tmp
	}

	fmt.Println(maxSatisfy(mainProducts, 0, n))
}

func maxSatisfy(mainProducts []Product, i int, n int) int {
	if n < 0 { // 先判断n再判断i
		return -(1 << 61)
	}

	if i == len(mainProducts) || n == 0 {
		return 0
	}

	if memo[n][i] != -666 {
		return memo[n][i]
	}

	choose := maxSatisfy(mainProducts, i+1, n-mainProducts[i].Price) + mainProducts[i].Price*mainProducts[i].Sat
	notChoose := maxSatisfy(mainProducts, i+1, n)

	chooseAttachOne := -1
	chooseAttachTwo := -1

	// 如果选择了第i个主件，那么就可以选择最多2个该主件的附件

	//	选1个附件
	index := mainProducts[i].Index
	attach := attachProducts[index]
	if len(attach) >= 1 {
		for first := 0; first < len(attach); first++ {
			tmp := maxSatisfy(mainProducts, i+1, n-mainProducts[i].Price-attach[first].Price) +
				mainProducts[i].Price*mainProducts[i].Sat + attach[first].Price*attach[first].Sat
			if tmp > chooseAttachOne {
				chooseAttachOne = tmp
			}
		}
	}

	//	选2个附件
	if len(attach) >= 2 {
		for first := 0; first < len(attach)-1; first++ {
			for second := first + 1; second < len(attach); second++ {
				tmp := maxSatisfy(mainProducts, i+1, n-mainProducts[i].Price-attach[first].Price-attach[second].Price) +
					mainProducts[i].Price*mainProducts[i].Sat + attach[first].Price*attach[first].Sat +
					attach[second].Price*attach[second].Sat

				if tmp > chooseAttachTwo {
					chooseAttachTwo = tmp
				}
			}
		}
	}
	
	memo[n][i] = max(notChoose, max(choose, max(chooseAttachOne, chooseAttachTwo)))
	return memo[n][i]
}

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