题解 | #购物单#

const [totalPrice, num] = readline().split(' ').map(Number);
function main(tp, num) {
  // 主件
  const mains = {};
  // 副件
  const subParts = {};
  for (let i = 1; i <= num; i++) {
    const [v, p, q] = readline().split(' ').map(Number);
    // 主件
    if (q == 0) {
      mains[i] = [v, p];
    } else {
      // 副件
      if (q in subParts) {
        // 第二个副件
        subParts[q].push([v, p]);
      } else {
        // 第一个副件
        subParts[q] = [[v, p]];
      }
    }
  }
  // w[i][j] 表示 i 号主件的第j种组合情况时的价格，j有4个值，表示主件及其副件可能的以下四种组合方式：
  // 1. 主件
  // 2. 主件+副件1
  // 3. 主件+副件2
  // 4. 主件+副件1+副件2
  const w = [];
  // v[i][j] 和 w[i][j] 对应，表示i号主件的第j种组合情况时的满意度，即价格*重要度
  const v = [];
  for (const i in mains) {
    // 只有主件时
    const _w = [mains[i][0]];
    const _v = [mains[i][0] * mains[i][1]];
    if (i in subParts) {
      const sub = subParts[i];
      // 主件+副件1
      _w.push(mains[i][0] + sub[0][0]);
      _v.push(mains[i][0] * mains[i][1] + sub[0][0] * sub[0][1]);
      if (sub.length > 1) {
        // 主件+副件2
        _w.push(mains[i][0] + sub[1][0]);
        _v.push(mains[i][0]*mains[i][1] + sub[1][0]*sub[1][1]);
        // 主件+副件1+副件2
        _w.push(mains[i][0] + sub[0][0] + sub[1][0]);
        _v.push(mains[i][0]*mains[i][1] + sub[0][0]*sub[0][1] + sub[1][0]*sub[1][1]);
      }
    }
    w.push(_w);
    v.push(_v);
  }
  // dp是(w+1)*(tp+1)的二维表， dp[i][j]表示，只拿前i个物品时，且总价不超过j时的最大满意度
//   const dp = [];
//   for (let i = 0; i <= w.length; i++) {
//     dp.push(new Array(tp+1).fill(0));
//   }
     // 时间复杂度O(w*tp)，空间复杂度O(w*tp)
//   for (let i = 0; i < w.length; i++) {
       // 
//     for (let j = 10; j <= tp; j += 10) {
//       // 不拿i号主件，这里dp[i + 1]是因为dp表第一行已经全部初始化为0了，所以在索引上和w相差1
//       let max = dp[i][j];
//       // 在i号主件的k种和副件的组合情况中，选择满意度最大的作为dp[i+1][j]的值
//       for (let k = 0; k < w[i].length; k++) {
//         if (j >= w[i][k]) {
//           max = Math.max(max, dp[i][j - w[i][k]] + v[i][k]);
//         }
//       }
//       dp[i+1][j] = max;
//     }
//   }
//   return dp[w.length][tp];
  // 优化空间复杂度到O(tp)
  const dp = new Array(tp+1).fill(0);
  for (let i = 0; i < w.length; i++) {
    for (let j = tp; j >= 0; j -= 10) {
      let max = dp[j];
      for (let k = 0; k < w[i].length; k++) {
        if (j >= w[i][k]) {
          max = Math.max(max, dp[j - w[i][k]] + v[i][k]);
        }
      }
      dp[j] = max;
    }
  }
  return dp[tp];
}
console.log(main(totalPrice, num));