CF1527E Partition Game

You are given an array $ a $ of $ n $ integers. Define the cost of some array $ t $ as follows: $ $$$cost(t) = \sum_{x \in set(t) } last(x) - first(x), $ $

where $ set(t) $ is the set of all values in $ t $ without repetitions, $ first(x) $ , and $ last(x) $ are the indices of the first and last occurrence of $ x $ in $ t $ , respectively. In other words, we compute the distance between the first and last occurrences for each distinct element and sum them up.

You need to split the array $ a $ into $ k $ consecutive segments such that each element of $ a$$$ belongs to exactly one segment and the sum of the cost of individual segments is minimum.

N/A

N/A

In the first example, we can divide the array into $ [1,6,6,4] $ and $ [6,6,6] $ . Cost of $ [1,6,6,4] $ will be $ (1-1) + (3 - 2) + (4-4) = 1 $ and cost of $ [6,6,6] $ will be $ 3-1 = 2 $ . Total cost would be $ 1 + 2 = 3 $ . In the second example, divide the array into $ [5,5],[5],[5,2,3] $ and $ [3] $ . Total Cost would be $ 1 + 0 + 0 + 0 = 1 $ .