CF2167G Mukhammadali and the Smooth Array

Muhammadali 有一个整数数组 $a_1, \dots, a_n$。他可以更改（替换）任意位置的元素；将第 $i$ 个位置更改成任何他希望的整数需要花费 $c_i$。他没有更改的位置必须保持原值。 在所有更改完成后，如果第 $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$。

对于每个测试用例，输出一个整数，表示消除所有“下降”所需的最小总花费。

在第一个和第二个样例中，数组本身已经没有“下降”，因此无需任何更改。 在第三个样例中，一种最优的数组是 $[2,3,5,6]$；要达成这个结果，除了第二个元素外，其他元素都需要被替换，因此答案是 $c_1 + c_3 + c_4 = 3$。 由 ChatGPT 5 翻译