A6929 | $Alice的石子合并$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

有一排从左到右的 $n$ 堆石子，初始依次编号为 $1,2,\dots,n$。 每个原始第 $i$ 堆自带一对属性 $(a_i, b_i)$（非负整数）。 你可以反复对相邻两堆进行合并，直到只剩下一堆。一次合并必须选择一对当前相邻的块 $X$（在左）与 $Y$（在右），并指定哪一方是主动方： - 右并左（右块主动）：将右块 $Y$ 并入左块 $X$。 本次费用为 $a_Y$（主动方当前携带的 $a$）。合并后，新块的属性完全继承被动方 $X$ 的属性。 - 左并右（左块主动）：将左块 $X$ 并入右块 $Y$。 本次费用为 $b_X$（主动方当前携带的 $b$）。合并后，新块的属性完全继承被动方 $Y$ 的属性。 请计算，将所有石子最终合并成一堆的最小总代价。

- 第一行一个整数 $n$。 - 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。 - 第三行 $n$ 个整数 $b_1,b_2,\dots,b_n$。

输出一个整数，为最小总代价。

输入 #1

5
5 2 6 3 4
9 4 8 1 2

输出 #1

数据范围 测试点$n$ 范围$a_i,b_i$ 范围$1\sim 2$$2\le n<20$$0\le a_i,b_i\le 10^{12}$$3\sim 6$$20\le n<500$$0\le a_i,b_i\le 10^{12}$$7\sim 20$$500\le n\le 2\times 10^{5}$$0\le a_i,b_i\le 10^{12}$ 样例解释 合并过程 第 1 次：右并左 * 操作：主动 $2$ 并到 被动 $1$ * 费用：$a_2=2$ * 继承：保留锚点 $1$ 的属性 * 新状态： [1..2]@1(a=5,b=9) | [3..3]@3(a=6,b=8) | [4..4]@4(a=3,b=1) | [5..5]@5(a=4,b=2) --- 第 2 次：右并左 * 操作：主动 $3$ 并到 被动 $1$ * 费用：$a_3=6$ * 继承：保留锚点 $1$ 的属性 * 新状态： [1..3]@1(a=5,b=9) | [4..4]@4(a=3,b=1) | [5..5]@5(a=4,b=2) --- 第 3 次：左并右 * 操作：主动 $4$ 并到 被动 $5$ * 费用：$b_4=1$ * 继承：保留锚点 $5$ 的属性 * 新状态： [1..3]@1(a=5,b=9) | [4..5]@5(a=4,b=2) --- 第 4 次：右并左 * 操作：主动 $5$ 并到 被动 $1$ * 费用：$a_5=4$ * 继承：保留锚点 $1$ 的属性 * 新状态： [1..5]@1(a=5,b=9)（完成）

C++ 编辑器

输入

输出