A16742. Mukhammadali and the Smooth Array
编程题
普及-
知识点
题目描述
Muhammadali 有一个整数数组 $a_1, \dots, a_n$。他可以更改（替换）任意位置的元素；将第 $i$ 个位置更改成任何他希望的整数需要花费 $c_i$。他没有更改的位置必须保持原值。
在所有更改完成后，如果第 $i$ 个位置的最终值严格大于第 $i+1$ 个位置的最终值（$1 \leq i < n$），那么我们称第 $i$ 个位置发生了“下降”。
Muhammadali 想让最终数组中没有“下降”发生。
请找出为了确保数组中不存在任何“下降”需要付出的最小代价。
在所有更改完成后，如果第 $i$ 个位置的最终值严格大于第 $i+1$ 个位置的最终值（$1 \leq i < n$），那么我们称第 $i$ 个位置发生了“下降”。
Muhammadali 想让最终数组中没有“下降”发生。
请找出为了确保数组中不存在任何“下降”需要付出的最小代价。
输入格式
第一行为一个整数 $t$（$1 \leq t \leq 5000$），表示测试用例的数量。
每个测试用例包含三行：
第一行包含一个整数 $n$（$1 \leq n \leq 8000$），表示数组的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），表示数组中的元素。
第三行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \leq c_i \leq 10^9$），表示更改各个位置的花费。
保证所有测试用例的 $n$ 之和不超过 $8000$。
每个测试用例包含三行：
第一行包含一个整数 $n$（$1 \leq n \leq 8000$），表示数组的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），表示数组中的元素。
第三行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \leq c_i \leq 10^9$），表示更改各个位置的花费。
保证所有测试用例的 $n$ 之和不超过 $8000$。
输出格式
对于每个测试用例，输出一个整数，表示消除所有“下降”所需的最小总花费。
输入输出样例
输入 #1
10 1 10 5 4 1 2 2 3 5 6 7 8 4 4 3 2 1 1 1 1 1 3 3 1 2 100 1 1 5 5 5 5 5 5 10 1 10 1 10 5 1 3 2 2 4 100 1 1 1 100 6 10 9 8 7 6 5 1 100 1 100 1 100 5 100 1 100 100 100 1 100 1 1 1 4 2 1 2 1 5 4 3 2 7 1 5 3 4 2 6 7 10 1 10 1 10 1 10
输出 #1
0 0 3 2 0 1 203 1 6 11
说明/提示
在第一个和第二个样例中，数组本身已经没有“下降”，因此无需任何更改。
在第三个样例中，一种最优的数组是 $[2,3,5,6]$；要达成这个结果，除了第二个元素外，其他元素都需要被替换，因此答案是 $c_1 + c_3 + c_4 = 3$。
在第三个样例中，一种最优的数组是 $[2,3,5,6]$；要达成这个结果，除了第二个元素外，其他元素都需要被替换，因此答案是 $c_1 + c_3 + c_4 = 3$。