#AT2018. F - Simple Operations on Sequence
F - Simple Operations on Sequence
当前没有测试数据。
F - 简单的操作序列
分数：500分
题目描述
给定两个序列 $A = (A_1, A_2, \ldots, A_N)$ 和 $B = (B_1, B_2 \ldots, B_N)$，都由 $N$ 个整数构成。
在序列 $A$ 上，你可以任意次数地按以下两种操作中的一种或多种进行操作（也可以不进行操作），并且可以按任意顺序进行。
- 选择一个整数 $i$ 满足 $1 \leq i \leq N$，将 $A_i$ 增加或减少 $1$，花费 $X$ 日元（日本货币）。
- 选择一个整数 $i$ 满足 $1 \leq i \leq N-1$，交换 $A_i$ 和 $A_{i+1}$ 的值，花费 $Y$ 日元。
输出使得序列 $A$ 变为序列 $B$ 的最小总花费。
限制
- $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$
- 输入中的所有值都是整数。
输入
从标准输入中按以下格式输入：
输出
输出使得 $A$ 变为 $B$ 的最小总花费。
4 3 5
4 2 5 2
6 4 2 1
16
初始时，有 $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)$。
这些操作的总花费为 $3+5+5+3 = 16$ 日元，是最小的。
5 12345 6789
1 2 3 4 5
1 2 3 4 5
0
起始时 $A$ 和 $B$ 相等，所以不需要进行操作。
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
13104119429316474
注意输入输出中的值可能不适合 $32$ 位整数类型。