#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「 뚫기

题目描述

在不久的将来,新加坡流行一种叫做「穿越」的游戏。游戏规则很简单:玩家需要控制一个楔形飞船从左到右穿过一个 N×MN \times M 的隧道。隧道中有 NN 个绿色障碍物阻挡飞船前进。障碍物位于每个格子的左侧墙壁上,跨越多个格子的连续障碍物被视为一个障碍物。为了方便描述,飞船前进的方向为 xx 轴,与之垂直的方向为 yy 轴。在相同的 xx 坐标上只能有一个障碍物。

例如,下图展示了一个 11×611 \times 6 的隧道,其中有 1111 个障碍物。最左边的障碍物从 (0,2)(0,2)(0,5)(0,5),最右边的障碍物从 (10,1)(10,1)(10,5)(10,5)

飞船在每个格子中可以进行两种移动之一。第一种移动是瞬移。瞬移是将飞船从当前格子移动到相同 xx 坐标的任意格子。无论移动到哪个格子,瞬移的费用始终为 AA。例如,下图展示了飞船从 (0,1)(0,1) 瞬移到 (0,5)(0,5) 的情况,费用为 AA

飞船的第二种移动是前进,费用为 00。即使前进方向上有障碍物,飞船也可以穿过障碍物,但这会产生费用 BB。例如,下图展示了飞船从 (6,5)(6,5) 前进到 (7,5)(7,5) 的情况,由于 (7,5)(7,5) 有障碍物,费用为 BB

当飞船完全穿过隧道时,游戏结束。游戏得分是飞船穿过隧道时产生的总费用。显然,得分越低越好。游戏开始时,玩家可以选择飞船的初始 yy 坐标,且不产生费用。游戏结束时,飞船的 yy 坐标无关紧要。

即使隧道的大小和障碍物的位置相同,费用 AABB 的变化也会影响游戏得分和飞船的最佳移动策略。你需要实现以下两个函数,利用给定的隧道大小和障碍物位置,在每次费用 AABB 变化时,计算可能的最低游戏得分。

void init(int N, int M, int Y1[], int Y2[]);
  • 该函数在程序开始时调用一次。
  • 参数 NNMM 表示隧道的大小 N×MN \times M
  • 参数 Y1Y1Y2Y2 是表示障碍物位置的数组,长度为 NN。如果从 (X,Y1[X])(X, Y_1[X])(X,Y2[X])(X, Y_2[X]) 有一个障碍物,则 Y1[X]Y1[X]Y2[X]Y2[X] 分别表示 Y1Y_1Y2Y_2
long long minimize(int A, int B);
  • 参数 AA 是飞船瞬移一次的费用,BB 是飞船穿过一次障碍物的费用。该函数返回飞船穿过隧道所需的最小费用。

你需要提交一个代码,该代码中实现以下函数:

void init(int N, int M, int Y1[], int Y2[]);
long long minimize(int A, int B);

这些函数应按照上述描述工作。当然,你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。

输入格式

示例评测程序按以下格式读取输入:

  • 11 行:NMQN\,M\,QN×MN \times M:隧道的大小,QQ:查询的数量)
  • 2+i (0iN1)2+i\ (0 \leq i \leq N-1) 行:Y1Y2Y_1\,Y_2xx 坐标为 ii 的障碍物的 yy 坐标位置从 Y1Y_1Y2Y_2
  • 2+N+i (0iQ1)2+N+i\ (0 \leq i \leq Q-1) 行:ABA\,BAA:瞬移费用,BB:穿过障碍物的费用)

输出格式

示例评测程序对每个查询调用你的代码中的 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) 11
minimize(3, 5) 33

数据范围

对于所有输入数据,满足:

  • 1N1041 \leq N \leq 10^4
  • 1M1091 \leq M \leq 10^{9}
  • 1Q1061 \leq Q \leq 10^{6}
  • 0Y1Y2M10 \leq Y_1 \leq Y_2 \leq M-1
  • 0A,B1090 \leq A, B \leq 10^{9}

详细子任务附加限制及分值如下表所示。

子任务编号 分值 子任务附加限制
11 77 Q=1,N3,000,M3,000Q=1, N \leq 3,000, M \leq 3,000
22 2222 Q50Q \leq 50
33 1919 N500N \leq 500
44 2121 N2,500N \leq 2,500
55 3131 无附加限制