CFCF2167G.Mukhammadali and the Smooth Array

普及-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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$ 。

输出格式

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

输入输出样例

输入#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

说明/提示

在第一个和第二个样例中，数组本身已经没有“下降”，因此无需任何更改。

在第三个样例中，一种最优的数组是 $[2,3,5,6]$ ；要达成这个结果，除了第二个元素外，其他元素都需要被替换，因此答案是 $c_1 + c_3 + c_4 = 3$ 。

首页