ZUFEOJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
Login
Register
1006: 打扑克
内存限制:128 MB
时间限制:1 S
标准输入输出
题目类型:传统
评测方式:文本比较
上传者:
提交:340
通过:26
提交
提交记录
统计
Web Board
题目描述
给定一摞 n 张扑克牌,每张牌上有两个值 a_i,b_i,有以下两种操作:
对于牌顶的牌 (a_top, b_top) ,从上到下将把包括他在内的 a_top 张牌扔掉并获得 b_top 的愉悦度。注意:如果牌堆里面没有 a_top 张牌的话不能进行此操作。
把牌堆顶的牌扔到这摞牌的最下面。
现在你可以进行无限次操作,也可以在任意时刻停下来,问你最多能获得多少愉悦度。
输入格式
第一行一个数字 n, 接下来 n 行从上到下描述每张牌:每行两个数字表示牌上两个数字 a_i,b_i。
输出格式
一行一个数,表示最多的愉悦值。
输入样例
复制
3 2 3 1 2 1 1
输出样例
复制
5
数据范围与提示
先选择第二张牌,然后再一次轮到第一张牌的时候选择第一张牌,然后没有牌了停下来,共获得了 2+3=5 的愉悦度
数据范围与提示
对于 100% 的数据,有 n <=10^3, a_i < n, b_i < 10^3。
分类标签
背包