AT_abc201_f [ABC201F] Insertion Sort

题目描述

有 $N$ 个人，编号为 $1$ 到 $N$，他们从左到右排成一列。最初，从左起第 $i$ 个人的编号为 $P_i$。

你的目标是通过重复以下三种操作，使得所有人从左到右按编号升序排列。这些操作可以以任意顺序进行任意多次（也可以不进行）。

• 选择一个整数 $i\ (1 \leq i \leq N)$，支付代价 $A_i$，将第 $i$ 个人 (id 为 $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$

输出格式

输出达到目标所需支付的总代价的最小值。

输入输出样例 #1

输入 #1

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

输出 #1

6

输入输出样例 #2

输入 #2

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

输出 #2

15

输入输出样例 #3

输入 #3

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

输出 #3

15865

输入输出样例 #4

输入 #4

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

输出 #4

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)$
• 所有输入均为整数

样例解释 1

只需支付代价 $C_3=6$，将第 $3$ 个人移动到最右端，即可使所有人按升序排列。不存在比这更低的总代价，因此答案为 $6$。

样例解释 2

按以下顺序操作可以达到最小总代价：

• 支付代价 $B_1=8$，将第 $1$ 个人移动到最左端。
• 支付代价 $C_5=5$，将第 $5$ 个人移动到最右端。
• 支付代价 $C_6=2$，将第 $6$ 个人移动到最右端。

由 ChatGPT 4.1 翻译