分数: 6 点
注意
与其他问题相比,这个问题需要更多的专业知识。
如果您没有完整解决方案的想法,建议先瞄准部分分数,然后继续下一个问题。
问题陈述
每个都有无限多个项目 N 类型。 i第一种类型的物品有重量 i 和值 v_i.
你被给予 Q 查询。在每个查询中,您都会得到一个正整数 W.
当您选择某些物品时,求最大可能的总价值,使得总重量恰好为 W.
约束
- 1 \leq N \leq 4000
- 1 \leq Q \leq 2 \times 10^5
- 0 \leq v_i \leq 10^9
- 1 \leq W \leq 10^9
- 所有输入值均为整数
部分分数
此题得分不全。
- 如果您使用以下方法求解数据集 N \leq 300,你会得到 4 点。
输入
输入由标准输入给出,格式如下:
N Q
v_1 v_2 \dots v_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询均按以下格式给出:
W
输出
打印 Q 行。上 i第行,输出答案 i-第一个查询。
示例输入 1
4 9 2 1 7 4 1 2 3 4 5 6 7 8 9
示例输出 1
2 4 7 9 11 14 16 18 21
例如,在第 6 个查询中, W=6.
如果您携带两件以下类型的物品 3,总值变为 7 + 7 = 14,这是最大值。
示例输入 2
10 10 104 231 361 478 661 765 963 1132 1402 1552 1 10 15 27 48 100 853822501 687675302 281611653 844033520
示例输出 2
104 1552 2213 4206 7460 15572 133006571782 107124530332 43868837466 131481666104