A2772 | 奶牛贝西
来源USACO / 2013
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
FJ给奶牛贝西的脚安装上了弹簧，使它可以在农场里快速地跳跃，但是它还没有学会如何降低速度。
FJ觉得让贝西在一条直线的一维线路上进行练习，他在不同的目标点放置了N (1 <= N <= 1000)个目标点，目标点i在目标点x(i)，该点得分为p(i)。贝西开始时可以选择站在一个目标点上，只允许朝一个方向跳跃，从一目标点跳到另外一个目标点，每次跳跃的距离至少和上一次跳跃的距离相等，并且必须跳到一个目标点。
每跳到一个目标点，贝西可以拿到该点的得分，请计算他的最大可能得分。
FJ觉得让贝西在一条直线的一维线路上进行练习，他在不同的目标点放置了N (1 <= N <= 1000)个目标点，目标点i在目标点x(i)，该点得分为p(i)。贝西开始时可以选择站在一个目标点上，只允许朝一个方向跳跃，从一目标点跳到另外一个目标点，每次跳跃的距离至少和上一次跳跃的距离相等，并且必须跳到一个目标点。
每跳到一个目标点，贝西可以拿到该点的得分，请计算他的最大可能得分。
输入格式
* 第 1 行：整数 N。
* 第 2..1+N 行：第 i+1 行包含 x（i） 和 p（i），每个都是 0..1,000,000 范围内的整数。
* 第 2..1+N 行：第 i+1 行包含 x（i） 和 p（i），每个都是 0..1,000,000 范围内的整数。
输出格式
* 第 1 行：Bessie 可以获得的最大积分数。
输入输出样例
输入 #1
6 5 6 1 1 10 5 7 6 4 8 8 10
输出 #1
25
有 6 个目标。第一个位于位置 x=5，值 6 点，依此类推。
Bessie 从位置 x=4（8 点）跳到位置 x=5（6 点）到位置 x=7（6 点）到位置 x=10（5 点）。
Bessie 从位置 x=4（8 点）跳到位置 x=5（6 点）到位置 x=7（6 点）到位置 x=10（5 点）。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？