← 返回题目
题库练习 Remove at the lowest cost
← 上一题 下一题 →

A16824 | Remove at the lowest cost

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

你有 $n$ 个元素。每个元素有一个自然值 $a_i$ 和一个自然删除代价 $c_i$。你需要将除一个以外的所有元素移除，并且总支付的费用最小。为此，你可以进行如下操作 $n-1$ 次：

每次操作，你选择两个相邻的元素，移除值较小的那个。在这次操作中，你需要支付这两个元素中删除代价较小的那一个。如果这两个元素的值相等，你可以移除任意一个，支付二者中较小的删除代价。移除一个元素后，其右侧的所有元素会向左移动一位，不留空隙。

你还有 $n$ 次将数组中某个元素删除代价变为 $0$ 的操作。第 $i$ 次操作后，下标为 $p_i$ 的元素的删除代价变为 $0$。保证所有 $p_i$ 互不相同。你需要分别求出原数组，以及每次将删除代价赋为 $0$ 之后的最小总移除费用。

注意：第 $i$ 次操作后，下标为 $p_i$ 的元素在之后所有问题（$i+1, i+2, \dots, n$）中的删除代价都保持为 $0$。

输入格式

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试数据组数。

每组测试数据的第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$），表示元素个数。

第二行包含 $n$ 个自然数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示每个元素的值。

第三行包含 $n$ 个自然数 $c_1, c_2, \ldots, c_n$（$1 \leq c_i \leq 10^9$），表示每个元素的移除代价。

第四行包含 $n$ 个自然数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$），表示在对应操作中，哪一个元素的移除代价会变成 $0$。保证所有 $p_i$ 互不相同。

保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每组测试数据，输出 $n+1$ 个数，分别表示在执行所有置零操作之前以及每次操作后，移除除一个外所有元素的最小总代价。

输入输出样例

输入 #1
2
10
5 5 8 10 4 3 4 10 5 5
10 3 9 6 9 8 7 8 10 3
1 10 2 9 5 6 7 4 3 8
4
1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000
1 2 4 3
输出 #1
42 36 30 30 30 12 12 12 0 0 0 
3000000000 0 0 0 0
C++ 编辑器
输入
输出