题目内容

小李负责公司的汽车采购业务。最近公司需要采购一批汽车，保证其可以载$X$人，承货$V$立方米。

小李调研了市场的$n$种汽车。对第$i$种汽车价值$m_i$元，有$k_i$种选配方案。默认的方案可以承载$x_i$人，承货$y_i$立方米。第$j$种选配方案需要金额变化为$m_{ij}$元，可以选配特殊的座椅或者支架使得载人和承货能力发生变化，载人变化值为$x_{ij}$，载货变化值为$y_{ij}$。每辆车只能选择一种选配方案，或者选择默认方案。

题解

题面描述

本题要求采购汽车以满足载人和载货的需求：至少载 $X$ 人和至少承载 $Y$ 立方米货物。市场上共有 $n$ 种汽车，每种汽车有一种默认方案和若干种选配方案。

• 对于第 $i$ 种汽车，默认方案的花费为 $m_i$ 元，载人能力为 $x_i$ 人，载货能力为 $y_i$ 立方米；
• 同时，第 $i$ 种汽车有 $k_i$ 种选配方案，每个选配方案会使得花费增加 $m_{ij}$ 元，载人能力变化 $x_{ij}$，载货能力变化 $y_{ij}$。

每辆车只能采用一种方案（默认或某个选配方案），且可以无限制地采购任意种汽车的任一方案。目标是在满足至少 $X$ 人和 $Y$ 立方米的条件下，花费最少金额。