Это простая версия задачи. Единственное различие между версиями заключается в ограничениях на \(t\), \(n\), \(k\).
У вас есть компьютер с двумя CPU. Также есть \(k\) программ, пронумерованных целыми числами от \(1\) до \(k\), которые вы можете исполнять на компьютере, каждую только на одном CPU.
\(i\)-я программа (\(1 \le i \le k\)) занимает \(cold_i\) секунд, чтобы быть исполненной на любом CPU. Однако, если последняя программа, которая исполнялась на этом CPU была также программа \(i\), исполнение занимает \(hot_i\) секунд (\(hot_i \le cold_i\)). Обратите внимание, что это выполняется, только если мы исполнили программу \(i\) несколько раз последовательно на этом CPU — если мы исполняем программу \(i\), потому другую программу, потом программу \(i\), время исполнения программы во второй раз займет \(cold_i\) секунд.
Вам дана последовательность \(a_1, a_2, \ldots, a_n\) длины \(n\), состоящая из целых чисел от \(1\) до \(k\). Вам нужно исполнить на компьютере программы \(a_1, a_2, \ldots, a_n\) в этом порядке. Для всех \(2 \le i \le n\), вы не можете начать исполнять программу \(a_i\), пока программа \(a_{i - 1}\) не завершилась.
Найдите минимальное количество времени нужное, чтобы исполнить все программы \(a_1, a_2, \ldots, a_n\) в таком порядке.
Выходные данные
Для каждого набора входных данных выведите минимальное время, необходимое чтобы исполнить все программы в данном порядке.
Примечание
В первом наборе входных данных мы можем сделать следующее:
- Исполнить программу \(a_1 = 1\) на CPU \(1\). Это займет \(cold_1 = 3\) секунды.
- Исполнить программу \(a_2 = 2\) на CPU \(2\). Это займет \(cold_2 = 2\) секунды.
- Исполнить программу \(a_3 = 2\) на CPU \(2\). Последняя программа, которая была исполнена на этом CPU была тоже программа \(2\), поэтому это займет \(hot_2 = 1\) секунду.
Суммарно нам потребуется \(3 + 2 + 1 = 6\) секунд, чтобы исполнить все программы. Можно показать, что это оптимальное время.
Во втором наборе входных данных мы можем сделать следующее:
- Исполнить программу \(a_1 = 1\) на CPU \(1\). Это займет \(cold_1 = 5\) секунд.
- Исполнить программу \(a_2 = 2\) на CPU \(2\). Это займет \(cold_2 = 3\) секунды.
- Исполнить программу \(a_3 = 1\) на CPU \(1\). Последняя программа, которая была исполнена на этом CPU была тоже программа \(1\), поэтому это займет \(hot_1 = 2\) секунды.
- Исполнить программу \(a_4 = 2\) on CPU \(2\). Последняя программа, которая была исполнена на этом CPU была тоже программа \(2\), поэтому это займет \(hot_2 = 1\) секунду.
Суммарно нам потребуется \(5 + 3 + 2 + 1 = 11\) секунд, чтобы исполнить все программы. Можно показать, что это оптимальное время.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
6
11
301
225
8
4999999996
11
6
63
|