Skip to content

13043: 【原3043】铁索连环

题目

题目描述

author: 董博男 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3043

Description

默默最近迷上了三国杀。三国杀是一种桌游,说的是三个国家之间的打打杀杀。

默默这几天在玩一种奇怪的类三国杀游戏。这个游戏是这样的:

有n个武将排成一排,这其中有的是忠臣,有的是反贼。

作为主公的你,可以每一轮把连续k个血量都大于等于k的人用铁索连起来,这样这一轮被连起来的k个人每人会受到k点伤害。

每人只能被铁索连一次。经过足够轮之后,主公得到的奖励值为对反贼的伤害总点数减去对忠臣的伤害总点数。

默默希望你能帮她解决这个有趣的问题,也就是给出主公能得到的最大的奖励值。

Input Format

第一行是一个整数n表示n个武将,n是1到10000范围内的整数。

以下n行每行两个整数x,y依次顺序表示每个武将的身份和血量。x=0为忠臣;x=1为反贼。y是0到1000之间的整数。

Output Format

输出只有一行,包含一个整数表示主公能得到的最大的奖励值。

Sample Input

8
1 5
0 4
1 5
0 2
1 3
0 3
0 1
1 6

Sample Output

5

About Testdata

40% 1<=n<=20
60% 1<=n<=1000
100% 1<=n<=10,000

Hints

尝试利用递推或者递归解题。

Limits

Time limit: 1000ms, memory limit: 50000kb.

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!