当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6804:Contest of Rope Pulling

题目描述
Rope Pulling, also known as Tug of War, is a classic game. Zhang3 organized a rope pulling contest between Class 1 and Class 2.

There are $n$ students in Class 1 and $m$ students in Class 2. The $i^\mathrm{th}$ student has strength $w_i$ and beauty-value $v_i$. Zhang3 needs to choose some students from both classes, and let those chosen from Class 1 compete against those chosen from Class 2. It is also allowed to choose no students from a class or to choose all of them.

To be a fair contest, the total strength of both teams must be equal. To make the contest more beautiful, Zhang3 wants to choose such a set of students, that the total beauty-value of all participants is maximized. Please help her determine the optimal total beauty-value.
输入解释
The first line of the input gives the number of test cases, $T \; (1 \le T \le 30)$. $T$ test cases follow.

For each test case, the first line contains two integers $n, m \; (1 \le n, m \le 1000)$, representing the number of students in Class 1 and Class 2.

Then $(n + m)$ lines follow, describing the students. The $i^\mathrm{th}$ line contains two integers $w_i, v_i \; (1 \le w_i \le 1000, \; -10^9 \le v_i \le 10^9)$, representing the strength and the beauty-value of the $i^\mathrm{th}$ student. The first $n$ students come from Class 1, while the other $m$ students come from Class 2.

The sum of $(n + m)$ in all test cases doesn't exceed $10^4$.
输出解释
For each test case, print a line with an integer, representing the optimal total beauty-value.
输入样例
2
3 4
4 7
3 8
2 2
1 4
5 8
1 3
4 4
1 2
1000 -10000
200 3000
800 5000
输出样例
30
0
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6804

最后修改于 2020-10-25T23:34:32+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
10000/5000MS(Java/Others) 524288/524288K(Java/Others)