← 返回题目列表

AtCoder · joi2017ho_d

D. 足球

中文机器翻译题面 查看原题

配点: 100 点

你是 JOI 联赛著名足球俱乐部的经理。

俱乐部有 N 名选手组成,选手有 1 减去 N 被标注了编号。选手们为了优胜每天在场地上练习。场地纵向 H 米,横向 W 它的形状为一米长方形。地面的垂直方向平行于南北方向,水平方向平行于东西方向。从地面西北角向南 i 向东米 j 指向您已行驶米数的点 我们称之为 (i, j) 。

练习结束后,练习用的球必须收起来。清理工作开始时,队员们 i (1 \leqq i \leqq N) 是一个点 (S_i, T_i) 并且球在玩家的位置 仅 1 仅有的 1 我有一个。你是一名玩家 N 带点 (S_N, T_N) ,你的任务是取回球,即将球放在 将其移至 (S_N, T_N) 即可完成清理。清洁过程中您不能移动。

你可以指挥玩家的行动。当玩家采取行动时,他们会根据该行动累积疲劳程度。

在以下动作中,控球球员可以执行动作(i)、(ii)和(iii),其他球员可以执行动作(ii)和(iv)。

(i) 北、南、东、西 4 方向不对 1 方向和正整数 指定 p 。朝那个方向踢球并准确击球 p 以米为单位移动。踢球的球员不会因该动作而移动,并且不再拥有球权。疲劳程度为 增加 A \times p + B 。
(ii) 北、南、东、西 4 方向不对 1 指定方向。朝那个方向 1 移动米。如果移动的球员有球,他就随球移动。有球或无球时的疲劳程度 C 。
(iii) 将球放在原地并处于您不再拥有球的状态。疲劳程度不会增加。
(iv) 控球。疲劳程度不会增加。此操作只能由与球处于同一位置的球员执行,并且只能在没有其他人控球的情况下执行。

请注意,如果球员或球离开场地,或者同一地点存在多个球员,这并不重要。

为了防止队员在练习后积累过多的疲劳,您决定找出队员因清理而产生的疲劳总量的最小可能值。

課題

给定场地的大小和球员的位置,编写一个程序,找出球员因清理而造成的最小可能总疲劳量。


入力

从标准输入读取以下输入。

  • 1 在线 2 整数 给出了 H, W 以空格作为分隔符。这些地面是垂直的 H 米,横向 W 这表示它的形状为 1 米长方形。
  • 2 线描述了疲劳程度的增加。 3 整数 给出了 A, B, C 以空格为分隔书写。
  • 3 行是一个整数 N 。这是播放器 N 这表明有人。
  • 继续 N 行 i 行目 (1 \leqq i \leqq N) 是 写入 2 整数 S_i, T_i 以空格作为分隔符。这些是清理开始时的玩家。 i 是重点 它代表处于 (S_i, T_i) 中。

出力

因清理而造成的玩家总疲劳程度的最小可能值被添加到标准输出中。 1 请按行输出。


制限

所有的输入数据满足以下条件。

  • 1 \leqq H \leqq 500.
  • 1 \leqq W \leqq 500.
  • 0 \leqq A \leqq 1\,000\,000\,000.
  • 0 \leqq B \leqq 1\,000\,000\,000.
  • 0 \leqq C \leqq 1\,000\,000\,000.
  • 2 \leqq N \leqq 100\,000.
  • 0 \leqq S i \leqq H (1 \leqq i \leqq N).
  • 0 \leqq Ti \leqq W (1 \leqq i \leqq N).
  • (S_1, T_1) \neq (S_N, T_N).

小課題

小課題 1 [5 点]

  • N = 2 很满意。

小課題 2 [30 点]

满足以下条件。

  • N \leqq 1\,000.
  • A = 0.

小課題 3 [65 点]

没有其他限制。


入力例 1

6 5
1 3 6
3
1 1
0 4
6 5

出力例 1

26

入力例 1 是一个小任务 1 和小作业 不满足 2 条件。在此输入示例中,接地处于如下所示的状态。图中,白色圆圈代表球员,黑色圆圈代表球。你是 我在 (6, 5) 。

グラウンドの初期状態

在这种情况下,您可以按照以下方式操作。

  1. 選手 1 将球向东移动。 3 踢米。疲劳程度为 球上升 1 \times 3 + 3 = 6 移至 (1, 4) 。
  2. 選手 2 向南 1 移动米并控球。疲劳程度为 它增加了 6 。
  3. 選手 2 向东 1 移动仪表。疲劳程度为 6 。
  4. 選手 2 将球向南移动。 5 踢米。疲劳程度为 球上升 1 \times 5 + 3 = 8 移至 (6, 5) 。

在这种情况下,总疲劳级别为 6 + 6 + 6 + 8 = 26 ,这是最小值。 满足条件

最適解における行動の様子


入力例 2

3 3
0 50 10
2
0 0
3 3

出力例 2

60

入力例 2 是一个小任务 1 和小作业 不满足 2 。输入示例 2 中无需踢球。


入力例 3

4 3
0 15 10
2
0 0
4 3

出力例 3

45

入力例 3 是一个小任务 1 和小作业 不满足 2 满足条件。


入力例 4

4 6
0 5 1000
6
3 1
4 6
3 0
3 0
4 0
0 4

出力例 4

2020

入力例 4 是一个小任务 1 条件,次要赋值为 2 满足条件。请注意,这包括同一位置有多个玩家的情况。