Дан массив из n чисел a1... an. Стоимостью подотрезка элементов в массиве назовем количество неупорядоченных пар различных позиций внутри подотрезка, содержащих одинаковые элементы. Разбейте массив на k непересекающихся непустых подотрезков таких, что сумма их стоимостей минимальна. Каждый элемент массива должен попасть ровно в один подотрезок.
Первая строка содержит два целых числа n и k (2 ≤ n ≤ 105, 2 ≤ k ≤ min (n, 20)) — размер массива и количество отрезков, на которые надо его разбить.
Следующая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ n) — элементы массива.
Выведите одно число — минимальную стоимость разбиения массива на подотрезки.
7 3
1 1 3 3 3 2 1
1
10 2
1 2 1 2 1 2 1 2 1 2
8
13 3
1 2 2 2 1 2 1 1 1 2 2 1 1
9
В первом примере оптимально разбить последовательность на три подпоследовательности: [1], [1, 3], [3, 3, 2, 1]. Стоимости равны 0, 0 и 1, поэтому ответ равен 1.
Во втором примере оптимально разбить подпоследовательность на две половины. Стоимость каждой половины равна 4.
В третьем примере оптимально разбить следующим образом: [1, 2, 2, 2, 1], [2, 1, 1, 1, 2], [2, 1, 1]. Стоимости равны 4, 4, 1.
Название |
---|