AT_abc232_f [ABC232F] Simple Operations on Sequence

题目描述

给定两个长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$ 和 $B = (B_1, B_2, \ldots, B_N)$。

对于整数序列 $A$，你可以任意次数（可以为 $0$ 次）重复执行以下两种操作之一：

• 选择满足 $1 \leq i \leq N$ 的整数 $i$，将 $A_i$ 的值加 $1$ 或减 $1$。该操作需要花费 $X$ 日元。
• 选择满足 $1 \leq i \leq N-1$ 的整数 $i$，交换 $A_i$ 和 $A_{i+1}$ 的值。该操作需要花费 $Y$ 日元。

通过上述操作，将整数序列 $A$ 变为与整数序列 $B$ 完全一致时，所需的最小总费用是多少？

输入格式

输入以如下格式从标准输入给出。

$N$ $X$ $Y$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$

输出格式

输出将 $A$ 变为 $B$ 所需的最小总费用。

输入输出样例 #1

输入 #1

4 3 5
4 2 5 2
6 4 2 1

输出 #1

16

输入输出样例 #2

输入 #2

5 12345 6789
1 2 3 4 5
1 2 3 4 5

输出 #2

0

输入输出样例 #3

输入 #3

18 20719114 5117250357733867
10511029 36397527 63027379 44706927 47672230 79861204 57882493 42931589 51053644 52300688 43971370 26515475 62139996 41282303 34022578 12523039 6696497 64922712
14720753 4621362 25269832 91410838 86751784 32741849 6602693 60719353 28911226 88280613 18745325 80675202 34289776 37849132 99280042 73760634 43897718 40659077

输出 #3

13104119429316474

说明/提示

限制条件

• $2 \leq N \leq 18$
• $1 \leq X \leq 10^8$
• $1 \leq Y \leq 10^{16}$
• $1 \leq A_i, B_i \leq 10^8$
• 所有输入均为整数

样例解释 1

初始时，$A = (4, 2, 5, 2)$。可以按如下方式进行操作，使 $A$ 变为 $B$：

• 支付 $X = 3$ 日元，将 $A_3$ 的值加 $1$。此时 $A = (4, 2, 6, 2)$。
• 支付 $Y = 5$ 日元，交换 $A_2$ 和 $A_3$ 的值。此时 $A = (4, 6, 2, 2)$。
• 支付 $Y = 5$ 日元，交换 $A_1$ 和 $A_2$ 的值。此时 $A = (6, 4, 2, 2)$。
• 支付 $X = 3$ 日元，将 $A_4$ 的值减 $1$。此时 $A = (6, 4, 2, 1) = B$。

上述操作的总费用为 $3 + 5 + 5 + 3 = 16$ 日元，这是最小值。

样例解释 2

$A$ 和 $B$ 从一开始就完全一致，因此无需进行任何操作。

样例解释 3

请注意，输入或输出可能超出 $32$ 位整数范围。

由 ChatGPT 4.1 翻译