2167G.md (2053B)
1 Source: https://codeforces.com/problemset/problem/2167/G 2 3 G. Mukhammadali and the Smooth Array 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Muhammadali has an integer array $a_1,\dots,a_n$. He can change (replace) any subset of positions; changing position $i$ costs $c_i$ and replaces $a_i$ with any integer of his choice. The positions that he does not change must retain their original values. 22 23 After all changes, we call an index $i$ ($1 \le i \lt n$) a drop if the final value at position $i$ is strictly greater than the final value at position $i+1$. Muhammadali wants the final array to contain no drops. 24 25 Find the minimum cost of changes required to ensure that there are no drops in the array. 26 27 Input 28 29 The first line contains an integer $t$ ($1 \le t \le 5000$) — the number of test cases. 30 31 Each test case consists of three lines: 32 33 The first line contains a single integer $n$ ($1 \le n \le 8000$) — the length of the arrays. 34 35 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array. 36 37 The third line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — the costs of changes. 38 39 It is guaranteed that the sum of $n$ across all test cases does not exceed $8000$. 40 41 Output 42 43 For each test case, output a single integer — the minimum possible total cost required to eliminate all drops. 44 45 Example 46 47 Input 48 49 ``` 50 10 51 52 1 53 54 10 55 56 5 57 58 4 59 60 1 2 2 3 61 62 5 6 7 8 63 64 4 65 66 4 3 2 1 67 68 1 1 1 1 69 70 3 71 72 3 1 2 73 74 100 1 1 75 76 5 77 78 5 5 5 5 5 79 80 10 1 10 1 10 81 82 5 83 84 1 3 2 2 4 85 86 100 1 1 1 100 87 88 6 89 90 10 9 8 7 6 5 91 92 1 100 1 100 1 100 93 94 5 95 96 100 1 100 100 100 97 98 1 100 1 1 1 99 100 4 101 102 2 1 2 1 103 104 5 4 3 2 105 106 7 107 108 1 5 3 4 2 6 7 109 110 10 1 10 1 10 1 10 111 ``` 112 113 Output 114 115 ``` 116 0 117 118 0 119 120 3 121 122 2 123 124 0 125 126 1 127 128 203 129 130 1 131 132 6 133 134 11 135 ``` 136 137 Note 138 139 In the first and second examples, the array already has no drops, so no changes are needed. 140 141 In the third example, one of the optimal arrays is: $[2,3,5,6]$; to achieve this, all elements except the second need to be replaced, so the answer is $c_1 + c_3 + c_4 = 3$.