Insertion Sort

题目描述

有 $N$ 人，他们的 ID 编号为 $1$ 到 $N$，从左到右站成一排。最初，从左数第 $i$ 个人的 ID 编号是 $P_i$。 你的目标是通过反复执行下面三种操作，将人按 ID 编号从左到右按升序重新排列。你可以任意次数（可以为零）以任意顺序执行这些操作。

选择一个整数 $i\ (1 \leq i \leq N)$，支付代价 $A_i$，将编号为 $i$ 的人（Person $i$）移动到你选择的任意位置。 选择一个整数 $i\ (1 \leq i \leq N)$，支付代价 $B_i$，将编号为 $i$ 的人移动到队列的左端。 选择一个整数 $i\ (1 \leq i \leq N)$，支付代价 $C_i$，将编号为 $i$ 的人移动到队列的右端。

在达到目标之前使你支付的总代价最小化。

输入格式

输入按以下格式由标准输入给出： $N$ $P_1$ $P_2$ $\ldots$ $P_N$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_N$ $B_N$ $C_N$

输出格式

输出在达到目标之前你需要支付的最小总代价。

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

6

6
2 6 5 3 4 1
10 8 16
30 2 10
10 17 8
11 27 22
8 6 5
15 29 2

15

9
3 8 4 7 6 9 1 5 2
7976 3696 9706
768 8807 8521
1133 8683 7120
1189 3331 2259
900 7451 1159
6126 2639 7107
5540 8253 2891
8417 4220 9091
8732 1417 1540

15865

12
11 9 1 12 2 7 3 5 10 4 6 8
3960 3158 9029
6521 6597 7581
5688 2299 2123
4946 4298 9122
394 4350 9142
3098 7151 2039
8525 3758 6155
6970 3658 9353
9780 1778 3608
6065 5562 923
9701 5524 6482
9395 6016 705

20637

提示

$1 \leq N \leq 2 \times 10^5$ $1 \leq P_i \leq N$ $1 \leq A_i,B_i,C_i \leq 10^9$ $P_i \neq P_j\ (i \neq j)$ 输入中的所有数值均为整数。你可以通过支付代价 $C_3=6$ 将 Person $3$ 移动到右端来将人按 ID 编号的升序重新排列。 没有比这更小的代价，因此答案是 $6$.
下面的操作序列使总代价最小化：

支付代价 $B_1=8$ 将 Person $1$ 移动到左端； 支付代价 $C_5=5$ 将 Person $5$ 移动到右端； 支付代价 $C_6=2$ 将 Person $6$ 移动到右端。

标签: AtCoder|abc201F

来源

AtCoder|abc201F