题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
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]);
}
})();
投递BOSS直聘等公司6个岗位