题解 | #购物单#

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    let line = await readline();
    let [totalAmount, kind] = line.split(" ").map(Number);
    let base = 10;
    let sum = totalAmount / base;

    let list = Array(kind + 1)
        .fill(0)
        .map((item) => {
            return { selfConfig: {}, fujian: [] };
        });
    for (let i = 1; i <= kind; i++) {
        line = await readline();
        let [price, weight, zhujianIndex] = line.split(" ").map(Number);
        list[i].selfConfig = {
            price: price / base,
            value: (price * weight) / base,
            isfujian:zhujianIndex ? true:false
        };
        if (zhujianIndex) {
            list[zhujianIndex].fujian.push({
                price: price / base,
                value: (price * weight) / base,
            });
        }
    }
    const dp = Array(kind + 1)
        .fill(0)
        .map((item) => Array(sum + 1).fill(0));

    for (let i = 1; i <= kind; i++) {
        for (let c = 1; c <= sum; c++) {
            if (c < list[i].selfConfig.price) {
                //没钱
                dp[i][c] = dp[i - 1][c];
                continue;
            }
            if (list[i].selfConfig.isfujian) {
                //单买附件
                dp[i][c] = dp[i - 1][c];
                continue;
            }
            // 主件
            //单买
            dp[i][c] = Math.max(
                dp[i - 1][c],
                dp[i - 1][c - list[i].selfConfig.price] +
                    list[i].selfConfig.value
            );
            // 买第一个附件
            if (list[i].fujian[0]) {
                let temp =
                    c - list[i].selfConfig.price - list[i].fujian[0].price;
                if (temp >= 0) {
                    dp[i][c] = Math.max(
                        dp[i][c],
                        dp[i - 1][temp] +
                            list[i].selfConfig.value +
                            list[i].fujian[0].value
                    );
                }
            }
            // 买第二个附件
            if (list[i].fujian[1]) {
                let temp =
                    c - list[i].selfConfig.price - list[i].fujian[1].price;
                if (temp >=0) {
                    dp[i][c] = Math.max(
                        dp[i][c],
                        dp[i - 1][temp] +
                            list[i].selfConfig.value +
                            list[i].fujian[1].value
                    );
                }
            }

            // 都买
            if (list[i].fujian[1] && list[i].fujian[0]) {
                let temp =
                    c -
                    list[i].selfConfig.price -
                    list[i].fujian[0].price -
                    list[i].fujian[1].price;
                if (temp >= 0) {
                    dp[i][c] = Math.max(
                        dp[i][c],
                        dp[i - 1][temp] +
                            list[i].selfConfig.value +
                            list[i].fujian[0].value +
                            list[i].fujian[1].value
                    );
                }
            }

        }
    }

    console.log(dp[kind][sum] *10)
})();