题解 | #购物单#

package main

import (
	"fmt"
)

func main() {
    money, n := 0, 0
    fmt.Scan(&money, &n)
    price := make(map[int][]int)
    value := make(map[int][]int)
    for i := 0; i < n; i++ {
        spand, val, index := 0, 0, 0
        fmt.Scan(&spand, &val, &index)
        
        if index == 0 {
            if  _, ok := price[i+1]; !ok {
                price[i+1] = make([]int, 3)
                value[i+1] = make([]int, 3)
            }
            price[i+1][0] = spand
            value[i+1][0] = val
        } else {
            if _, ok := price[index]; !ok {
                price[index] = make([]int, 3)
                value[index] = make([]int, 3)
            }
            if price[index][1] == 0 {
                price[index][1] = spand
                value[index][1] = val
            } else {
                price[index][2] = spand
                value[index][2] = val
            }
        }
    }
    dp := make([]int, money+1)
    for i := 0; i <= n; i++ {
        if len(price[i]) == 0 {
            continue
        }
        for j := money; j >= price[i][0]; j-- {
            dp[j] = max(dp[j], dp[j-price[i][0]]+price[i][0]*value[i][0])
            if price[i][1] != 0 && price[i][0] + price[i][1] <= j {
                dp[j] = max(dp[j], dp[j-price[i][0]-price[i][1]]+price[i][0]*value[i][0]+price[i][1]*value[i][1])
            }
            if price[i][2] != 0 && j >= price[i][0]+price[i][2] {
				dp[j] = max(dp[j], dp[j-price[i][0]-price[i][2]]+price[i][0]*value[i][0]+price[i][2]*value[i][2])
			}
			if price[i][1] != 0 && price[i][2] != 0 && j >= price[i][0]+price[i][1]+price[i][2] {
				dp[j] = max(dp[j], dp[j-price[i][0]-price[i][1]-price[i][2]]+price[i][0]*value[i][0]+price[i][1]*value[i][1]+price[i][2]*value[i][2])
			}
        }
    }
    fmt.Print(dp[money])
}

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