#P11706. 「KTSC 2020 R1」穿越
「KTSC 2020 R1」穿越
题目背景
请使用 C++17 或 C++20 提交本题
你需要在程序开头加入如下代码:
#include <vector>
void init(int N, int M, std::vector<int> Y1, std::vector<int> Y2);
long long minimize(int A, int B);
题目译自 2020년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T2「 뚫기」
题目描述
在不久的将来,新加坡流行一种叫做「穿越」的游戏。游戏规则很简单:玩家需要控制一个楔形飞船从左到右穿过一个 的隧道。隧道中有 个绿色障碍物阻挡飞船前进。障碍物位于每个格子的左侧墙壁上,跨越多个格子的连续障碍物被视为一个障碍物。为了方便描述,飞船前进的方向为 轴,与之垂直的方向为 轴。在相同的 坐标上只能有一个障碍物。
例如,下图展示了一个 的隧道,其中有 个障碍物。最左边的障碍物从 到 ,最右边的障碍物从 到 。
飞船在每个格子中可以进行两种移动之一。第一种移动是瞬移。瞬移是将飞船从当前格子移动到相同 坐标的任意格子。无论移动到哪个格子,瞬移的费用始终为 。例如,下图展示了飞船从 瞬移到 的情况,费用为 。
飞船的第二种移动是前进,费用为 。即使前进方向上有障碍物,飞船也可以穿过障碍物,但这会产生费用 。例如,下图展示了飞船从 前进到 的情况,由于 有障碍物,费用为 。
当飞船完全穿过隧道时,游戏结束。游戏得分是飞船穿过隧道时产生的总费用。显然,得分越低越好。游戏开始时,玩家可以选择飞船的初始 坐标,且不产生费用。游戏结束时,飞船的 坐标无关紧要。
即使隧道的大小和障碍物的位置相同,费用 和 的变化也会影响游戏得分和飞船的最佳移动策略。你需要实现以下两个函数,利用给定的隧道大小和障碍物位置,在每次费用 和 变化时,计算可能的最低游戏得分。
void init(int N, int M, int Y1[], int Y2[]);
- 该函数在程序开始时调用一次。
- 参数 和 表示隧道的大小 。
- 参数 和 是表示障碍物位置的数组,长度为 。如果从 到 有一个障碍物,则 和 分别表示 和 。
long long minimize(int A, int B);
- 参数 是飞船瞬移一次的费用, 是飞船穿过一次障碍物的费用。该函数返回飞船穿过隧道所需的最小费用。
你需要提交一个代码,该代码中实现以下函数:
void init(int N, int M, int Y1[], int Y2[]);
long long minimize(int A, int B);
这些函数应按照上述描述工作。当然,你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。
输入格式
示例评测程序按以下格式读取输入:
- 第 行:(:隧道的大小,:查询的数量)
- 第 行:( 坐标为 的障碍物的 坐标位置从 到 )
- 第 行:(:瞬移费用,:穿过障碍物的费用)
输出格式
示例评测程序对每个查询调用你的代码中的 minimize()
函数,并输出返回值。
3 5 2
2 4
0 2
1 3
2 1
3 5
1
3
提示
样例说明 #1
函数调用 | 返回值 |
---|---|
init(3, 5, {2, 0, 1}, {4, 2, 3}) |
|
minimize(2, 1) |
|
minimize(3, 5) |
数据范围
对于所有输入数据,满足:
详细子任务附加限制及分值如下表所示。
子任务编号 | 分值 | 子任务附加限制 |
---|---|---|
无附加限制 |