luogu#P11239. 「KTSC 2024 R2」跳跃游戏
「KTSC 2024 R2」跳跃游戏
题目背景
请使用 C++17 或 C++20 提交
你需要在程序开头加入如下代码:
#include<vector>
long long play_game(long long N, int Q, long long K, std::vector<long long> L, std::vector<long long> R);
题目描述
题目译自 2024년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T2 「점프 게임」
KOI 公司推出的跳跃游戏是一款通过多次跳跃穿越 个踏板的游戏。具体来说,游戏中有 个踏板按顺序排列在一条直线上,每个踏板从左到右依次编号为 。游戏开始时,主角站在最左边的 号踏板上,初始得分为 。
对于每个 ,主角可以选择走一步或跳跃。如果选择走一步,主角将移动到 号踏板,得分不变。如果选择跳跃,主角将移动到 号踏板,得分增加 。其中 是预先设定的常数。游戏在主角到达 号踏板的右侧时成功结束。也就是说,主角到达编号为 的踏板时,游戏结束——这些编号大于等于 的踏板实际上不存在,但表示主角已经越过了 号踏板。游戏的目标是通过合理控制主角的行动,使得分最大化并成功结束游戏。
喜欢网络直播的尚赫偶尔会玩 KOI 公司的跳跃游戏。虽然他自己玩得很开心,但观众们却反应平平。跳跃游戏不受欢迎的原因在于游戏非常困难且枯燥。首先,这款游戏的踏板数量可以多达 个。其次,即使是 KOI 公司的优秀开发者也无法设计出如此多的踏板,因此他们采用了一种相对简单的方法来生成每个踏板。开发者们最初将所有 设置为 ,然后进行 次操作:对于每个 ,他们选择一个区间 ,将 的值增加 。所有操作完成后的数组 就是游戏中每个踏板跳跃时获得的得分。
你是一名制作计算机科学视频的创作者,决定制作一个关于如何以最高得分完成 KOI 公司的跳跃游戏的视频。你认为这个视频会在尚赫的观众中大受欢迎,但你担心游戏规模太大,难以找到高效的算法。克服所有困难,在给定的 5 小时内成为这款游戏的高手吧!
你需要实现以下函数:
long long play_game(long long N, int Q, long long K, std::vector<long long> L, std::vector<long long> R);
N
:游戏中存在的踏板数量。Q
:开发者执行的操作次数。K
:跳跃后到达的下一个踏板的编号。L, R
:大小为 的整数数组。- 该函数返回一个整数,表示跳跃游戏结束时可以获得的最高得分。
- 该函数在每个测试点中只会被调用一次。
输入格式
示例评测程序按以下格式读取输入:
- 第 行:
- 第 行:
输出格式
示例评测程序按以下格式输出:
- 第 行:
play_game
返回的值
3 5 2
0 2
0 2
1 1
1 1
1 1
5
250 8 50
0 200
40 140
49 49
50 150
100 190
149 199
199 199
75 249
17
250 8 49
0 200
40 140
49 49
50 150
100 190
149 199
199 199
75 249
19
100 6 50
0 99
0 70
0 10
20 30
40 50
60 70
6
1000000000000 2 1
0 999999999999
0 999999999999
2000000000000
提示
对于所有输入数据,满足:
- 对于所有 ,
详细子任务附加限制及分值如下表所示。
子任务 | 分值 | 附加限制 |
---|---|---|
无附加限制 |