题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
input := bufio.NewScanner(os.Stdin)
input.Scan()
d := input.Text()
str := strings.Split(d, " ")
N, _ := strconv.Atoi(str[0]) //钱
//m, _ := strconv.Atoi(str[1]) //物品数量
first := make(map[int][2]int)//主键
second := make(map[int][]int)//附件
//现在要把多个物品归类，分别放到first,second里面
i:=1
for input.Scan() {
d := input.Text()
str := strings.Split(d, " ")
data1, _ := strconv.Atoi(str[0])
data2, _ := strconv.Atoi(str[1])
if str[2] == "0" {
//说明他是主键
first[i] = [2]int{data1, data2}
} else {
//说明他是附件
//判断是不是第一个附件
t, _ := strconv.Atoi(str[2])
_, ok := second[t]
if !ok {
second[t] = make([]int, 0)
second[t] = append(second[t], data1, data2)
} else {
second[t] = append(second[t], data1, data2)
}
}
i++
}
all := make(map[int][][2]int)
//分类完毕以后把让他们跟随附属物品然后计算一个总价格和对应的满意度
//根据主键分
for key, value := range first {
all[key] = make([][2]int, 1)
all[key][0][0] = value[0]
all[key][0][1] = value[1]*value[0]
//判断该主是否有副
_, ok := second[key]
if ok {
all[key] = append(all[key], [2]int{value[0]+second[key][0],value[0]*value[1]+ second[key][0]*second[key][1]})
if len(second[key]) == 4 {
all[key] = append(all[key], [2]int{value[0]+second[key][2],value[0]*value[1]+ second[key][2]*second[key][3]})
all[key] = append(all[key],[2]int{value[0]+second[key][0]+second[key][2],value[0]*value[1]+ second[key][0]*second[key][1]+second[key][2]*second[key][3]})
}
}
}
//我不知道怎么开辟一个数组可以用变量导入我是个废物
dp := make([]int,0)
for i:=0;i<=N;i++{
dp = append(dp, 0)
}
//所有物件处理完毕，开始动态规划
for _,value:= range all{
for i:=N;i>=0;i=i-10{
//这边只是根据题求了10的倍数，但是最好可以求以下商品的公因数，说不定会比10要大
for _,j:=range value{
if i - j[0]>=0{
if dp[i]<dp[i-j[0]]+j[1]{
dp[i] = dp[i-j[0]]+j[1]
}
}
}
}
}
fmt.Println(dp[N])
}
