CF155B.Combination
普及-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Ilya plays a card game by the following rules.
A player has several cards. Each card contains two non-negative integers inscribed, one at the top of the card and one at the bottom. At the beginning of the round the player chooses one of his cards to play it. If the top of the card contains number a__i, and the bottom contains number b__i, then when the player is playing the card, he gets a__i points and also gets the opportunity to play additional b__i cards. After the playing the card is discarded.
More formally: let's say that there is a counter of the cards that can be played. At the beginning of the round the counter equals one. When a card is played, the counter decreases by one for the played card and increases by the number b__i, which is written at the bottom of the card. Then the played card is discarded. If after that the counter is not equal to zero, the player gets the opportunity to play another card from the remaining cards. The round ends when the counter reaches zero or the player runs out of cards.
Of course, Ilya wants to get as many points as possible. Can you determine the maximum number of points he can score provided that you know his cards?
伊利亚按照以下规则玩一种纸牌游戏。
玩家手中持有若干张牌。每张牌上印有两个非负整数:一个位于牌的上方,另一个位于牌的下方。在一轮游戏开始时,玩家需从自己的牌中选择一张打出。若打出的牌上方数字为 ai,下方数字为 bi,则玩家打出该牌时获得 ai 分,并额外获得 bi 次出牌机会。打出后的牌将被弃掉。
更形式化地描述如下:设一个计数器用于记录当前还可打出的牌数。在一轮开始时,该计数器初始值为 1。每当打出一张牌时,计数器先减 1(表示消耗一次出牌机会),再增加 bi(即该牌下方所写的数字)。随后该牌被弃掉。若此时计数器值不为 0,则玩家可继续从剩余未打出的牌中选择一张打出。当计数器减至 0 或玩家已无剩余牌可打时,本轮结束。
显然,伊利亚希望获得尽可能多的分数。已知他手中的所有牌,你能计算出他最多能获得多少分吗?
输入格式
The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of cards Ilya has.
Each of the next n lines contains two non-negative space-separated integers — a__i and b__i (0 ≤ a__i, b__i ≤ 104) — the numbers, written at the top and the bottom of the i-th card correspondingly.
第一行包含一个整数 n(1≤n≤1000)—— 表示伊利亚拥有的卡片数量。
接下来的 n 行中,每行包含两个用空格分隔的非负整数 ai 和 bi(0≤ai,bi≤104)—— 分别表示第 i 张卡片正面和背面所写的数字。
输出格式
Print the single number — the maximum number of points you can score in one round by the described rules.
输出单个数字——按照所述规则,你在一轮中能够获得的最高分数。
输入输出样例
输入#1
2 1 0 2 0
输出#1
2
输入#2
3 1 0 2 0 0 2
输出#2
3
说明/提示
In the first sample none of two cards brings extra moves, so you should play the one that will bring more points.
In the second sample you should first play the third card that doesn't bring any points but lets you play both remaining cards.
在第一个样例中,两张卡片均不会带来额外的移动次数,因此你应该选择能带来更高分数的那张卡片。
在第二个样例中,你应该首先打出第三张卡片;这张卡片本身不带来任何分数,但允许你打出剩余的两张卡片。
输入解题思路,AI测评打分。不知道怎么写?