题解 | #购物单#

package main

import (
	"fmt"
)

type Product struct{
	v int
	p int
	q int
	ann []Product
}

func main(){
	var N,m int
	fmt.Scan(&N,&m)

	nums:=make([]Product,m)
	de:=make([]int,0)

	for i:=0;i<m;i++{//读取多行输入
		var a,b,c int
		fmt.Scan(&a,&b,&c)
		//fmt.Println(len(s[2]))
		//fmt.Println(a,b,c)
		temp:=Product{a/10,b,c,nil}
		nums[i]=temp
	}
	// 	fmt.Println(nums)
	for i:=0;i<len(nums);i++{//处理附属关系
		if nums[i].q!=0{
			nums[nums[i].q-1].ann=append(nums[nums[i].q-1].ann,nums[i])
			de=append(de,i)
		}
	}
	for j,i:= range de {//生成只有主物件存在的切片
		nums=append(nums[:i-j],nums[i-j+1:]...)
	}
	//fmt.Println(nums)
	m=len(nums)
	w,v:=make([][]int,0),make([][]int,0)//存储每个节点可能存在的组合购买情况
	for i:=0;i<m;i++ {//遍历得到主物件的组合购买情况
		w_temp,v_temp:=make([]int,0),make([]int,0)
		w_temp = append(w_temp, nums[i].v)
		v_temp = append(v_temp, nums[i].p*nums[i].v)
		for j:=0;j<len(nums[i].ann);j++{
			w_temp = append(w_temp, nums[i].v+nums[i].ann[j].v)
			v_temp = append(v_temp, nums[i].p*nums[i].v+nums[i].ann[j].v*nums[i].ann[j].p)
			if j==1{
				w_temp = append(w_temp, nums[i].v+nums[i].ann[0].v+nums[i].ann[1].v)
				v_temp = append(v_temp, nums[i].p*nums[i].v+nums[i].ann[0].v*nums[i].ann[0].p+nums[i].ann[1].v*nums[i].ann[1].p)
			}
		}
		w = append(w, w_temp)
		v = append(v, v_temp)
	}
	dp:=make([][]int,m+1)//定义dp数组，i为加入主物件的编号，j为当前所用的金额总数。
	for i:=0;i<m+1;i++{
		dp[i]=make([]int,N/10+1)
	}
	for i:=1;i<m+1;i++{//把一个一个主物件加入购买队列，计算最高的利益
		for j:=0;j<N/10+1;j=j+1{
			max_i:=dp[i-1][j]//在核对购买附属情况前要先用一个中间变量存储当前的最高利益，已确保最终该变量就是对应最高利益。
			for k:=0;k<len(w[i-1]);k++{
				if j-w[i-1][k]>=0{
					max_i=max(max_i,dp[i-1][j-w[i-1][k]]+v[i-1][k])
				}
			dp[i][j]=max_i
			}
		}
	}
	fmt.Printf("%d",dp[m][N/10]*10)


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

}