310201: CF1799D1. Hot Start Up (easy version)
Memory Limit：512 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Hot Start Up (easy version)
题意翻译
有两个 CPU 和 $k$ 种程序，你可以在 CPU 上运行程序。 如果你选择的 CPU 上一次运行的程序不是你当前运行的程序，则需要花费 $cold_i$ 的时间。 否则，需要花费 $hot_i$ 的时间。 现在有 $n$ 个程序需要运行，第 $i$ 次需要运行的程序类型为 $a_i$，每次可以任意选择一个 CPU 运行程序，一个 CPU 同一时间最多运行一个程序。 求最短运行完全部程序的时间。 共有 $t$ 组数据。 $1 \le n,k \le 5000$，$1 \le hot_i \le cold_i \le 10^9$，$1 \le a_i \le k$，$1 \le t \le 5000$，$\sum k \le 5000$，$\sum n \le 5000$题目描述
This is an easy version of the problem. The constraints of $ t $ , $ n $ , $ k $ are the only difference between versions. You have a device with two CPUs. You also have $ k $ programs, numbered $ 1 $ through $ k $ , that you can run on the CPUs. The $ i $ -th program ( $ 1 \le i \le k $ ) takes $ cold_i $ seconds to run on some CPU. However, if the last program we ran on this CPU was also program $ i $ , it only takes $ hot_i $ seconds ( $ hot_i \le cold_i $ ). Note that this only applies if we run program $ i $ multiple times consecutively — if we run program $ i $ , then some different program, then program $ i $ again, it will take $ cold_i $ seconds the second time. You are given a sequence $ a_1, a_2, \ldots, a_n $ of length $ n $ , consisting of integers from $ 1 $ to $ k $ . You need to use your device to run programs $ a_1, a_2, \ldots, a_n $ in sequence. For all $ 2 \le i \le n $ , you cannot start running program $ a_i $ until program $ a_{i - 1} $ has completed. Find the minimum amount of time needed to run all programs $ a_1, a_2, \ldots, a_n $ in sequence.输入输出格式
输入格式
Input consists of multiple test cases. The first line contains a single integer $ t $ , the number of test cases ( $ 1 \le t \le 5000 $ ). The first line of each test case contains $ n $ and $ k $ ( $ 1 \le n, k \le 5000 $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le k $ ). The third line of each test case contains $ k $ integers $ cold_1, cold_2, \ldots, cold_k $ ( $ 1 \le cold_i \le 10^9 $ ). The fourth line of each test case contains $ k $ integers $ hot_1, hot_2, \ldots, hot_k $ ( $ 1 \le hot_i \le cold_i $ ). It is guaranteed the sum of $ n $ and the sum of $ k $ over all test cases do not exceed $ 5000 $ .
输出格式
For each test case, print the minimum time needed to run all programs in the given order.
输入输出样例
输入样例 #1
9
3 2
1 2 2
3 2
2 1
4 2
1 2 1 2
5 3
2 1
4 3
1 2 3 1
100 100 100
1 1 1
5 2
2 1 2 1 1
65 45
54 7
5 3
1 3 2 1 2
2 2 2
1 1 1
5 1
1 1 1 1 1
1000000000
999999999
5 6
1 6 1 4 1
3 6 4 1 4 5
1 1 1 1 4 1
1 3
3
4 5 6
1 2 3
8 3
3 3 3 1 2 3 2 1
10 10 8
10 10 5输出样例 #1
6
11
301
225
8
4999999996
11
6
63说明
In the first test case, we can do the following: - Run program $ a_1 = 1 $ on CPU $ 1 $ . It takes $ cold_1 = 3 $ seconds to run. - Run program $ a_2 = 2 $ on CPU $ 2 $ . It takes $ cold_2 = 2 $ seconds to run. - Run program $ a_3 = 2 $ on CPU $ 2 $ . The last program run on this CPU was also program $ 2 $ , so it takes $ hot_2 = 1 $ second to run. In total, we need $ 3 + 2 + 1 = 6 $ seconds to run them all. We can show this is optimal. In the second test case, we can use do the following: - Run program $ a_1 = 1 $ on CPU $ 1 $ . It takes $ cold_1 = 5 $ seconds to run. - Run program $ a_2 = 2 $ on CPU $ 2 $ . It takes $ cold_2 = 3 $ seconds to run. - Run program $ a_3 = 1 $ on CPU $ 1 $ . The last program run on this CPU was also program $ 1 $ , so it takes $ hot_1 = 2 $ seconds to run. - Run program $ a_4 = 2 $ on CPU $ 2 $ . The last program run on this CPU was also program $ 2 $ , so it takes $ hot_2 = 1 $ second to run. In total, we need $ 5 + 3 + 2 + 1 = 11 $ seconds. We can show this is optimal.Input
题意翻译
有两个 CPU 和 $k$ 种程序，你可以在 CPU 上运行程序。 如果你选择的 CPU 上一次运行的程序不是你当前运行的程序，则需要花费 $cold_i$ 的时间。 否则，需要花费 $hot_i$ 的时间。 现在有 $n$ 个程序需要运行，第 $i$ 次需要运行的程序类型为 $a_i$，每次可以任意选择一个 CPU 运行程序，一个 CPU 同一时间最多运行一个程序。 求最短运行完全部程序的时间。 共有 $t$ 组数据。 $1 \le n,k \le 5000$，$1 \le hot_i \le cold_i \le 10^9$，$1 \le a_i \le k$，$1 \le t \le 5000$，$\sum k \le 5000$，$\sum n \le 5000$Output
**热启动（简单版）**
**题意翻译**：
你有两个 CPU 和 $k$ 种程序可以在 CPU 上运行。
如果你选择的 CPU 上一次运行的程序不是你当前运行的程序，则需要花费 $cold_i$ 的时间。
否则，需要花费 $hot_i$ 的时间。
现在有 $n$ 个程序需要运行，第 $i$ 次需要运行的程序类型为 $a_i$，每次可以任意选择一个 CPU 运行程序，一个 CPU 同一时间最多运行一个程序。
求最短运行完全部程序的时间。
共有 $t$ 组数据。
$1 \le n,k \le 5000$，$1 \le hot_i \le cold_i \le 10^9$，$1 \le a_i \le k$，$1 \le t \le 5000$，$\sum k \le 5000$，$\sum n \le 5000$。
**题目描述**：
这是一个简单版本的问题。$ t $, $ n $, $ k $ 的限制是不同版本之间的唯一区别。
你有一个带有两个 CPU 的设备。你有 $ k $ 个程序，编号从 $ 1 $ 到 $ k $，你可以在 CPU 上运行这些程序。
第 $ i $ 个程序（$ 1 \le i \le k $）在某些 CPU 上运行需要 $ cold_i $ 秒。但是，如果我们在这个 CPU 上运行的最后一个程序也是程序 $ i $，它只需要 $ hot_i $ 秒（$ hot_i \le cold_i $）。注意，这仅适用于我们连续多次运行程序 $ i $ 的情况——如果我们运行程序 $ i $，然后运行某个不同的程序，然后再运行程序 $ i $，那么第二次运行它将需要 $ cold_i $ 秒。
给你一个长度为 $ n $ 的序列 $ a_1, a_2, \ldots, a_n $，由从 $ 1 $ 到 $ k $ 的整数组成。你需要使用你的设备按顺序运行程序 $ a_1, a_2, \ldots, a_n $。对于所有 $ 2 \le i \le n $，你不能在程序 $ a_{i - 1} $ 完成之前开始运行程序 $ a_i $。
找出按给定顺序运行所有程序 $ a_1, a_2, \ldots, a_n $ 所需的最短时间。
**输入输出格式**：
**输入格式**：
输入由多个测试用例组成。第一行包含一个整数 $ t $，表示测试用例的数量（$ 1 \le t \le 5000 $）。
每个测试用例的第一行包含 $ n $ 和 $ k $（$ 1 \le n, k \le 5000 $）。
每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le k $）。
每个测试用例的第三行包含 $ k $ 个整数 $ cold_1, cold_2, \ldots, cold_k $（$ 1 \le cold_i \le 10^9 $）。
每个测试用例的第四行包含 $ k $ 个整数 $ hot_1, hot_2, \ldots, hot_k $（$ 1 \le hot_i \le cold_i $）。
保证所有测试用例的 $ n $ 之和和 $ k $ 之和不超过 $ 5000 $。
**输出格式**：
对于每个测试用例，打印按给定顺序运行所有程序所需的最短时间。**热启动（简单版）** **题意翻译**： 你有两个 CPU 和 $k$ 种程序可以在 CPU 上运行。 如果你选择的 CPU 上一次运行的程序不是你当前运行的程序，则需要花费 $cold_i$ 的时间。 否则，需要花费 $hot_i$ 的时间。 现在有 $n$ 个程序需要运行，第 $i$ 次需要运行的程序类型为 $a_i$，每次可以任意选择一个 CPU 运行程序，一个 CPU 同一时间最多运行一个程序。 求最短运行完全部程序的时间。 共有 $t$ 组数据。 $1 \le n,k \le 5000$，$1 \le hot_i \le cold_i \le 10^9$，$1 \le a_i \le k$，$1 \le t \le 5000$，$\sum k \le 5000$，$\sum n \le 5000$。 **题目描述**： 这是一个简单版本的问题。$ t $, $ n $, $ k $ 的限制是不同版本之间的唯一区别。 你有一个带有两个 CPU 的设备。你有 $ k $ 个程序，编号从 $ 1 $ 到 $ k $，你可以在 CPU 上运行这些程序。 第 $ i $ 个程序（$ 1 \le i \le k $）在某些 CPU 上运行需要 $ cold_i $ 秒。但是，如果我们在这个 CPU 上运行的最后一个程序也是程序 $ i $，它只需要 $ hot_i $ 秒（$ hot_i \le cold_i $）。注意，这仅适用于我们连续多次运行程序 $ i $ 的情况——如果我们运行程序 $ i $，然后运行某个不同的程序，然后再运行程序 $ i $，那么第二次运行它将需要 $ cold_i $ 秒。 给你一个长度为 $ n $ 的序列 $ a_1, a_2, \ldots, a_n $，由从 $ 1 $ 到 $ k $ 的整数组成。你需要使用你的设备按顺序运行程序 $ a_1, a_2, \ldots, a_n $。对于所有 $ 2 \le i \le n $，你不能在程序 $ a_{i - 1} $ 完成之前开始运行程序 $ a_i $。 找出按给定顺序运行所有程序 $ a_1, a_2, \ldots, a_n $ 所需的最短时间。 **输入输出格式**： **输入格式**： 输入由多个测试用例组成。第一行包含一个整数 $ t $，表示测试用例的数量（$ 1 \le t \le 5000 $）。 每个测试用例的第一行包含 $ n $ 和 $ k $（$ 1 \le n, k \le 5000 $）。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le k $）。 每个测试用例的第三行包含 $ k $ 个整数 $ cold_1, cold_2, \ldots, cold_k $（$ 1 \le cold_i \le 10^9 $）。 每个测试用例的第四行包含 $ k $ 个整数 $ hot_1, hot_2, \ldots, hot_k $（$ 1 \le hot_i \le cold_i $）。 保证所有测试用例的 $ n $ 之和和 $ k $ 之和不超过 $ 5000 $。 **输出格式**： 对于每个测试用例，打印按给定顺序运行所有程序所需的最短时间。
**题意翻译**：
你有两个 CPU 和 $k$ 种程序可以在 CPU 上运行。
如果你选择的 CPU 上一次运行的程序不是你当前运行的程序，则需要花费 $cold_i$ 的时间。
否则，需要花费 $hot_i$ 的时间。
现在有 $n$ 个程序需要运行，第 $i$ 次需要运行的程序类型为 $a_i$，每次可以任意选择一个 CPU 运行程序，一个 CPU 同一时间最多运行一个程序。
求最短运行完全部程序的时间。
共有 $t$ 组数据。
$1 \le n,k \le 5000$，$1 \le hot_i \le cold_i \le 10^9$，$1 \le a_i \le k$，$1 \le t \le 5000$，$\sum k \le 5000$，$\sum n \le 5000$。
**题目描述**：
这是一个简单版本的问题。$ t $, $ n $, $ k $ 的限制是不同版本之间的唯一区别。
你有一个带有两个 CPU 的设备。你有 $ k $ 个程序，编号从 $ 1 $ 到 $ k $，你可以在 CPU 上运行这些程序。
第 $ i $ 个程序（$ 1 \le i \le k $）在某些 CPU 上运行需要 $ cold_i $ 秒。但是，如果我们在这个 CPU 上运行的最后一个程序也是程序 $ i $，它只需要 $ hot_i $ 秒（$ hot_i \le cold_i $）。注意，这仅适用于我们连续多次运行程序 $ i $ 的情况——如果我们运行程序 $ i $，然后运行某个不同的程序，然后再运行程序 $ i $，那么第二次运行它将需要 $ cold_i $ 秒。
给你一个长度为 $ n $ 的序列 $ a_1, a_2, \ldots, a_n $，由从 $ 1 $ 到 $ k $ 的整数组成。你需要使用你的设备按顺序运行程序 $ a_1, a_2, \ldots, a_n $。对于所有 $ 2 \le i \le n $，你不能在程序 $ a_{i - 1} $ 完成之前开始运行程序 $ a_i $。
找出按给定顺序运行所有程序 $ a_1, a_2, \ldots, a_n $ 所需的最短时间。
**输入输出格式**：
**输入格式**：
输入由多个测试用例组成。第一行包含一个整数 $ t $，表示测试用例的数量（$ 1 \le t \le 5000 $）。
每个测试用例的第一行包含 $ n $ 和 $ k $（$ 1 \le n, k \le 5000 $）。
每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le k $）。
每个测试用例的第三行包含 $ k $ 个整数 $ cold_1, cold_2, \ldots, cold_k $（$ 1 \le cold_i \le 10^9 $）。
每个测试用例的第四行包含 $ k $ 个整数 $ hot_1, hot_2, \ldots, hot_k $（$ 1 \le hot_i \le cold_i $）。
保证所有测试用例的 $ n $ 之和和 $ k $ 之和不超过 $ 5000 $。
**输出格式**：
对于每个测试用例，打印按给定顺序运行所有程序所需的最短时间。**热启动（简单版）** **题意翻译**： 你有两个 CPU 和 $k$ 种程序可以在 CPU 上运行。 如果你选择的 CPU 上一次运行的程序不是你当前运行的程序，则需要花费 $cold_i$ 的时间。 否则，需要花费 $hot_i$ 的时间。 现在有 $n$ 个程序需要运行，第 $i$ 次需要运行的程序类型为 $a_i$，每次可以任意选择一个 CPU 运行程序，一个 CPU 同一时间最多运行一个程序。 求最短运行完全部程序的时间。 共有 $t$ 组数据。 $1 \le n,k \le 5000$，$1 \le hot_i \le cold_i \le 10^9$，$1 \le a_i \le k$，$1 \le t \le 5000$，$\sum k \le 5000$，$\sum n \le 5000$。 **题目描述**： 这是一个简单版本的问题。$ t $, $ n $, $ k $ 的限制是不同版本之间的唯一区别。 你有一个带有两个 CPU 的设备。你有 $ k $ 个程序，编号从 $ 1 $ 到 $ k $，你可以在 CPU 上运行这些程序。 第 $ i $ 个程序（$ 1 \le i \le k $）在某些 CPU 上运行需要 $ cold_i $ 秒。但是，如果我们在这个 CPU 上运行的最后一个程序也是程序 $ i $，它只需要 $ hot_i $ 秒（$ hot_i \le cold_i $）。注意，这仅适用于我们连续多次运行程序 $ i $ 的情况——如果我们运行程序 $ i $，然后运行某个不同的程序，然后再运行程序 $ i $，那么第二次运行它将需要 $ cold_i $ 秒。 给你一个长度为 $ n $ 的序列 $ a_1, a_2, \ldots, a_n $，由从 $ 1 $ 到 $ k $ 的整数组成。你需要使用你的设备按顺序运行程序 $ a_1, a_2, \ldots, a_n $。对于所有 $ 2 \le i \le n $，你不能在程序 $ a_{i - 1} $ 完成之前开始运行程序 $ a_i $。 找出按给定顺序运行所有程序 $ a_1, a_2, \ldots, a_n $ 所需的最短时间。 **输入输出格式**： **输入格式**： 输入由多个测试用例组成。第一行包含一个整数 $ t $，表示测试用例的数量（$ 1 \le t \le 5000 $）。 每个测试用例的第一行包含 $ n $ 和 $ k $（$ 1 \le n, k \le 5000 $）。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le k $）。 每个测试用例的第三行包含 $ k $ 个整数 $ cold_1, cold_2, \ldots, cold_k $（$ 1 \le cold_i \le 10^9 $）。 每个测试用例的第四行包含 $ k $ 个整数 $ hot_1, hot_2, \ldots, hot_k $（$ 1 \le hot_i \le cold_i $）。 保证所有测试用例的 $ n $ 之和和 $ k $ 之和不超过 $ 5000 $。 **输出格式**： 对于每个测试用例，打印按给定顺序运行所有程序所需的最短时间。