题解 | #购物单#

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

void (async function () {
    // Write your code here
    while ((line = await readline())) {
        let linearr = line.split(" ").map(Number);
        let w = linearr[0];
        let alldata = [];
        let f = [[]];
        for (let i = 0; i < linearr[1]; i++) {
            while ((line2 = await readline())) {
                let val = line2.split(" ").map(Number);
                alldata.push({
                    price: val[0],
                    importance: val[1],
                    parents: val[2],
                    childrens: [],
                });
            }
        }
        for (let i = 0; i < alldata.length; i++) {
            if (alldata[i].parents > 0) {
                alldata[alldata[i].parents - 1].childrens.push(alldata[i]);
            }
        }
        let usedata = [];
        for (let i of alldata) {
            if (i.parents == 0) {
                usedata.push(i);
            }
        }
        for (let i in usedata) {
            usedata[i].childrens.sort((a, b) => {
                return a.price - b.price;
            });
        }
        let n = usedata.length;
        for (let i = 0; i <= w; i += 10) {
            if (i < usedata[0].price) {
                f[0][i / 10] = 0;
            } else if (usedata[0].childrens.length == 0) {
                f[0][i / 10] = usedata[0].price * usedata[0].importance;
            } else {
                if (
                    i >= usedata[0].price &&
                    i < usedata[0].childrens[0].price + usedata[0].price
                ) {
                    f[0][i / 10] = usedata[0].price * usedata[0].importance;
                } else if (
                    usedata[0].childrens[1] &&
                    i >= usedata[0].childrens[0].price + usedata[0].price &&
                    i < usedata[0].price + usedata[0].childrens[1].price
                ) {
                    f[0][i / 10] =
                        usedata[0].price * usedata[0].importance +
                        usedata[0].childrens[0].price *
                            usedata[0].childrens[0].importance;
                } else if (
                    usedata[0].childrens[1] &&
                    i <
                        usedata[0].childrens[1].price +
                            usedata[0].price +
                            usedata[0].childrens[0].price &&
                    i >= usedata[0].price + usedata[0].childrens[1].price
                ) {
                    let one =
                        usedata[0].price * usedata[0].importance +
                        usedata[0].childrens[0].price *
                            usedata[0].childrens[0].importance;
                    let two =
                        usedata[0].price * usedata[0].importance +
                        usedata[0].childrens[1].price *
                            usedata[0].childrens[1].importance;
                    f[0][i / 10] = Math.max(one, two);
                } else if (
                    usedata[0].childrens[1] &&
                    i >=
                        usedata[0].childrens[0].price +
                            usedata[0].price +
                            usedata[0].childrens[1].price
                ) {
                    f[0][i / 10] =
                        usedata[0].price * usedata[0].importance +
                        usedata[0].childrens[0].price *
                            usedata[0].childrens[0].importance +
                        usedata[0].childrens[1].price *
                            usedata[0].childrens[1].importance;
                } else {
                    f[0][i / 10] =
                        usedata[0].price * usedata[0].importance +
                        usedata[0].childrens[0].price *
                            usedata[0].childrens[0].importance;
                }
            }
        }

        for (let i = 0; i <= w; i += 10) {
            for (let j = 1; j < n; j++) {
                if (!f[j]) f.push([]);
                if (i < usedata[j].price) {
                    f[j][i / 10] = f[j - 1][i / 10];
                } else if (usedata[j].childrens.length == 0) {
                    f[j][i / 10] = Math.max(
                        f[j - 1][i / 10],
                        usedata[j].price * usedata[j].importance +
                            f[j - 1][(i - usedata[j].price) / 10]
                    );
                } else {
                    if (
                        i >= usedata[j].price &&
                        i < usedata[j].childrens[0].price + usedata[j].price
                    ) {
                        f[j][i / 10] = Math.max(
                            f[j - 1][i / 10],
                            usedata[j].price * usedata[j].importance +
                                f[j - 1][(i - usedata[j].price) / 10]
                        );
                    } else if (
                        usedata[j].childrens[1] &&
                        i >= usedata[j].childrens[0].price + usedata[j].price &&
                        i < usedata[j].price + usedata[j].childrens[1].price
                    ) {
                        f[j][i / 10] = Math.max(
                            f[j - 1][i / 10],
                            usedata[j].price * usedata[j].importance +
                                usedata[j].childrens[0].price *
                                    usedata[j].childrens[0].importance +
                                f[j - 1][
                                    (i -
                                        usedata[j].price -
                                        usedata[j].childrens[0].price) /
                                        10
                                ],
                            usedata[j].price * usedata[j].importance +
                                f[j - 1][(i - usedata[j].price) / 10]
                        );
                    } else if (
                        usedata[j].childrens[1] &&
                        i <
                            usedata[j].childrens[0].price +
                                usedata[j].price +
                                usedata[j].childrens[1].price &&
                        i >= usedata[0].price + usedata[j].childrens[1].price
                    ) {
                        let one =
                            usedata[j].price * usedata[j].importance +
                            usedata[j].childrens[0].price *
                                usedata[j].childrens[0].importance +
                            f[j - 1][
                                (i -
                                    usedata[j].price -
                                    usedata[j].childrens[0].price) /
                                    10
                            ];
                        let two =
                            usedata[j].price * usedata[j].importance +
                            usedata[j].childrens[1].price *
                                usedata[j].childrens[1].importance +
                            f[j - 1][
                                (i -
                                    usedata[j].price -
                                    usedata[j].childrens[1].price) /
                                    10
                            ];
                        let three =
                            usedata[j].price * usedata[j].importance +
                            f[j - 1][(i - usedata[j].price) / 10];
                        f[j][i / 10] = Math.max(
                            f[j - 1][i / 10],
                            one,
                            two,
                            three
                        );
                    } else if (
                        usedata[j].childrens[1] &&
                        i >=
                            usedata[j].childrens[0].price +
                                usedata[j].price +
                                usedata[j].childrens[1].price
                    ) {
                        let one =
                            usedata[j].price * usedata[j].importance +
                            usedata[j].childrens[0].price *
                                usedata[j].childrens[0].importance +
                            usedata[j].childrens[1].price *
                                usedata[j].childrens[1].importance +
                            f[j - 1][
                                (i -
                                    usedata[j].price -
                                    usedata[j].childrens[0].price -
                                    usedata[j].childrens[1].price) /
                                    10
                            ];
                        let two =
                            usedata[j].price * usedata[j].importance +
                            f[j - 1][(i - usedata[j].price) / 10];
                        let three =
                            usedata[j].price * usedata[j].importance +
                            usedata[j].childrens[0].price *
                                usedata[j].childrens[0].importance +
                            f[j - 1][
                                (i -
                                    usedata[j].price -
                                    usedata[j].childrens[0].price) /
                                    10
                            ];
                        let four =
                            usedata[j].price * usedata[j].importance +
                            usedata[j].childrens[1].price *
                                usedata[j].childrens[1].importance +
                            f[j - 1][
                                (i -
                                    usedata[j].price -
                                    usedata[j].childrens[1].price) /
                                    10
                            ];
                        f[j][i / 10] = Math.max(
                            f[j - 1][i / 10],
                            one,
                            two,
                            three,
                            four
                        );
                    } else {
                        //f[j][i/10] = Math.max(f[j-1][i/10], usedata[j].price*usedata[j].importance + f[j-1][(i - usedata[j].price-usedata[j].childrens[0].price)/10]);
                        let one =
                            usedata[j].price * usedata[j].importance +
                            f[j - 1][(i - usedata[j].price) / 10];
                        let two =
                            usedata[j].price * usedata[j].importance +
                            usedata[j].childrens[0].price *
                                usedata[j].childrens[0].importance +
                            f[j - 1][
                                (i -
                                    usedata[j].price -
                                    usedata[j].childrens[0].price) /
                                    10
                            ];
                        f[j][i / 10] = Math.max(f[j - 1][i / 10], one, two);
                    }
                }
            }
        }
        console.log(f[n - 1][w / 10]);
    }
})();