题库 信息学奥赛题库 题目列表 信息学奥赛练习题:楼间跳跃【题目描述】在一条街道上...
问答题

信息学奥赛练习题:楼间跳跃

【题目描述】

在一条街道上有n栋楼,第i栋有hi层,每层都有价值为vi的物品。

Lyra可以花费一单位时间在同一栋楼中向上或向下走一层。特别地,每栋楼里都有一个大滑梯,只能从顶楼通往一楼,所以如果Lyra在顶层,可以花费一单位时间通过滑梯到达一楼(注意只有在顶楼才可以使用滑梯)。

Lyra还可以在不同的楼之间跳跃,即花费一单位时间从当前楼移动到相邻楼的同层,如果相邻楼没有Lyra当前位置高,则会落到相邻楼的顶层。

初始时Lyra在第一栋楼的顶层,她有m单位时间可以移动,Lyra拿去物品不需要时间,且一个物品被拿一次之后就会消失。

Lyra想知道她能获得的总价值最多是多少?

【输入】

第一行两个正整数n,m。

以下n行每行两个整数表示hi和vi

提示:输入数据较大,请采用快速的读入方式。

 

【输出】

输出一行一个整数表示最大的总价值。

 

【输入样例】

3 3

2 1

1 5

3 4

【输出样例】

14

【提示】

【数据规模及约定】

对于20%的数据,Σhi≤20。

对于另外10%的数据,vi=1。

对于另外30%的数据,Σhi≤1000。

对于另外20%的数据,n,hi≤105

对于100%的数据,n,hi≤106

题目信息
完善程序 2023年 练习
-
正确率
0
评论
288
点击