题解 | #购物单#

import java.util.Scanner;

fun main()  {
        val read = Scanner(System.`in`)
    val res = read.nextLine().split(' ').map {
        it.toInt()
    }
    fun max(a1: Int, a2: Int) = Math.max(a1, a2)
    val bu = res[0]
    val m = res[1]
    val goods = Array(m) { Good() }
    for (i in 0 until m) {
        val tri = read.nextLine().split(' ').map {
            it.toInt()
        }
        val v = tri[0]
        val p = tri[1]
        val q = tri[2]
        goods[i].v = v
        goods[i].p = v * p
        goods[i].q = q
        if (q != 0) {
            goods[q - 1].apply {
                if (a1 == -1) {
                    a1 = i
                } else {
                    a2 = i
                }
            }
        }
    }

    val dp = Array<Int>(bu + 1) { 0 }
    for (i in 1..m) {
        val good = goods[i - 1]
        for (j in bu downTo 0 step 10) {
            if (good.isMain.not())
                continue
            if (j >= good.v) {
                dp[j] = max(dp[j], dp[j - good.v] + good.p)
            }
            if (good.a1 != -1 && j >= (good.v + goods[good.a1].v)) {
                val a1 = goods[good.a1]
                dp[j] = max(dp[j], dp[j - good.v - a1.v] + good.p + a1.p)
            }
            if (good.a2 != -1 && j >= (good.v + goods[good.a2].v)) {
                val a2 = goods[good.a2]
                dp[j] = max(dp[j], dp[j - good.v - a2.v] + good.p + a2.p)
            }
            if (good.a1 != -1 && good.a2 != -1 && j >= (good.v + goods[good.a1].v + goods[good.a2].v)) {
                val a1 = goods[good.a1]
                val a2 = goods[good.a2]
                dp[j] = max(dp[j], dp[j - good.v - a1.v - a2.v] + good.p + a1.p + a2.p)
            }
        }
    }
    println(dp[bu])
}

data class Good(var v: Int = 0, var p: Int = 0, var q: Int = 0, var a1: Int = -1, var a2: Int = -1)

val Good.isMain: Boolean
    get() = q == 0