#CW50. 非常规约束背包(weight)

非常规约束背包(weight)

题目描述

有 NN 件物品,第 ii 件物品的重量和价值分别为 wiw_i 与 viv_i。它们满足超递增条件:对每个 i≥2i \ge 2,都有 ∑j=1i−1wj<wi\sum_{j=1}^{i-1} w_j < w_i。请选出总重量不超过 WW 的物品,使总价值最大。

输入格式

从 weight.in 文件读入数据。

第一行是测试组数 TT。每组数据先给出 N,WN, W,随后 NN 行每行输入 wi,viw_i, v_i。

输出格式

将结果输出到 weight.out 文件。

输出 TT 行,第 tt 行是第 tt 组数据的最大总价值。

样例 1 输入

3
3 10
1 2
3 1
9 3
3 20
1 2
3 1
9 3
4 15
1 1
3 2
5 3
10 4

样例 1 输出

5
6
7

数据范围

保证 1≤T≤2×1051 \le T \le 2\times 10^5,1≤N≤601 \le N \le 60,1≤wi≤W≤10181 \le w_i \le W \le 10^{18},1≤vi≤10161 \le v_i \le 10^{16},且 ∑j=1i−1wj<wi\sum_{j=1}^{i-1} w_j < w_i(2≤i≤N2 \le i \le N)。所有测试组中 NN 的总和不超过 2×1052\times 10^5。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 10 1∼41\sim 4 N≤20N \le 20
2 20 5∼85\sim 8 N≤30N \le 30
3 30 9∼149\sim 14 N≤60N \le 60
4 40 15∼2015\sim 20 满足全部限制,且所有测试组总规模受限