AT_abc328_g [ABC328G] Cut and Reorder

题目描述

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

你可以对数列 $A$ 进行如下两种操作，操作的顺序和次数均不限：

• 可以在任意位置将 $A$ 分割，并将分割后的各段自由重新排列。每分割一次（即每增加一个分割点）需要花费 $C$ 的代价。具体来说，花费 $(X-1)C$ 的代价，可以任选一个长度为 $X+1$ 的分割点序列 $(i_0,i_1,i_2,\ldots,i_X)\ (0=i_0<i_1<i_2<\cdots<i_X=N)$ 和 $(1,2,\ldots,X)$ 的任意排列 $p$，然后将 $(A_{i_{p_j-1}+1},A_{i_{p_j-1}+2},\ldots,A_{i_{p_j}})$ 按照 $j$ 的升序依次连接，得到新的 $A$。
• 可以任选 $A$ 的一个元素和一个整数 $k$，将该元素加上 $k$，花费 $|k|$ 的代价。

请你通过若干次操作，使得最终 $A$ 和 $B$ 完全相同，求所需总代价的最小值。

输入格式

输入以如下格式从标准输入读入：

$N$ $C$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

5 1
3 1 4 1 5
9 2 6 5 3

输出 #1

12

输入输出样例 #2

输入 #2

5 1000000000
3 1 4 1 5
9 2 6 5 3

输出 #2

15

输入输出样例 #3

输入 #3

22 467772225675200
814424018890229 837987908732596 281175505732576 405797525366223 319378664987871 305374284356649 519144936694626 316916938328237 590332737480143 506785561790072 945769796193819 365498597798550 5386616044591 672368930784037 478017750715806 340276460237787 176509793332130 2734777402752 677509027289850 250325127275409 260270543315523 103584313625431
720386673780641 77160494100361 540947273460639 255177791002759 969333325196025 477751866935037 369600749728569 466236682780196 343161112138696 541310338013515 42740499599240 165778332156355 618106559852784 16582487395877 591851763813728 221861304303645 982850624742022 728669467505250 337968530842725 746724490610504 61587851254728 451153536869240

输出 #3

4370668608634071

说明/提示

限制条件

• $1\leq N\leq 22$
• $1\leq C\leq 10^{15}$
• $1\leq A_i\leq 10^{15}\ (1\leq i\leq N)$
• $1\leq B_i\leq 10^{15}\ (1\leq i\leq N)$
• 输入均为整数

样例解释 1

例如，可以通过如下操作使 $A$ 和 $B$ 相等：

• 给 $A_2$ 加上 $2$，花费 $2$，$A=(3,3,4,1,5)$。
• 给 $A_4$ 加上 $1$，花费 $1$，$A=(3,3,4,2,5)$。
• 给 $A_3$ 加上 $3$，花费 $3$，$A=(3,3,7,2,5)$。
• 将 $A$ 分割为 $(3,3)$ 和 $(7,2,5)$，并交换顺序，花费 $1$，$A=(7,2,5,3,3)$。
• 给 $A_3$ 加上 $1$，花费 $1$，$A=(7,2,6,3,3)$。
• 给 $A_4$ 加上 $2$，花费 $2$，$A=(7,2,6,5,3)$。
• 给 $A_1$ 加上 $2$，花费 $2$，$A=(9,2,6,5,3)$。

总代价为 $2+1+3+1+1+2+2=12$。无法用 $11$ 或更少的代价使 $A$ 和 $B$ 相等，因此输出 $12$。

样例解释 2

例如，可以通过如下操作使 $A$ 和 $B$ 相等：

• 给 $A_1$ 加上 $6$，花费 $6$，$A=(9,1,4,1,5)$。
• 给 $A_2$ 加上 $1$，花费 $1$，$A=(9,2,4,1,5)$。
• 给 $A_3$ 加上 $2$，花费 $2$，$A=(9,2,6,1,5)$。
• 给 $A_4$ 加上 $4$，花费 $4$，$A=(9,2,6,5,5)$。
• 给 $A_5$ 加上 $-2$，花费 $2$，$A=(9,2,6,5,3)$。

总代价为 $15$。无法用 $14$ 或更少的代价使 $A$ 和 $B$ 相等，因此输出 $15$。

样例解释 3

输入和答案可能超出 $32\operatorname{bit}$ 整数范围。

由 ChatGPT 4.1 翻译