{"problem":{"name":"F. Yet Another Minimization Problem","description":{"content":"You are given an array of _n_ integers _a_1... _a__n_. The cost of a subsegment is the number of unordered pairs of distinct indices within the subsegment that contain equal elements. Split the given ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF868F"},"statements":[{"statement_type":"Markdown","content":"You are given an array of _n_ integers _a_1... _a__n_. The cost of a subsegment is the number of unordered pairs of distinct indices within the subsegment that contain equal elements. Split the given array into _k_ non-intersecting non-empty subsegments so that the sum of their costs is minimum possible. Each element should be present in exactly one subsegment.\n\n## Input\n\nThe first line contains two integers _n_ and _k_ (2 ≤ _n_ ≤ 105, 2 ≤ _k_ ≤ _min_ (_n_, 20)) — the length of the array and the number of segments you need to split the array into.\n\nThe next line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ _n_) — the elements of the array.\n\n## Output\n\nPrint single integer: the minimum possible total cost of resulting subsegments.\n\n[samples]\n\n## Note\n\nIn the first example it's optimal to split the sequence into the following three subsegments: \\[1\\], \\[1, 3\\], \\[3, 3, 2, 1\\]. The costs are 0, 0 and 1, thus the answer is 1.\n\nIn the second example it's optimal to split the sequence in two equal halves. The cost for each half is 4.\n\nIn the third example it's optimal to split the sequence in the following way: \\[1, 2, 2, 2, 1\\], \\[2, 1, 1, 1, 2\\], \\[2, 1, 1\\]. The costs are 4, 4, 1.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给定一个包含 #cf_span[n] 个整数的数组 #cf_span[a1... an]。一个子段的代价是该子段内满足不同下标但元素相等的无序对的数量。将给定数组划分为 #cf_span[k] 个互不相交且非空的子段，使得它们的代价之和最小。每个元素必须恰好属于一个子段。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[2 ≤ n ≤ 105], #cf_span[2 ≤ k ≤ min (n, 20)]) —— 数组的长度和你需要将数组划分成的子段数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ n]) —— 数组的元素。\n\n请输出一个整数：所得子段的最小可能总代价。\n\n在第一个例子中，最优方案是将序列划分为以下三个子段：#cf_span[[1]], #cf_span[[1, 3]], #cf_span[[3, 3, 2, 1]]。它们的代价分别为 #cf_span[0], #cf_span[0] 和 #cf_span[1]，因此答案为 #cf_span[1]。\n\n在第二个例子中，最优方案是将序列划分为两个相等的半部分。每半部分的代价为 #cf_span[4]。\n\n在第三个例子中，最优方案是将序列按以下方式划分：#cf_span[[1, 2, 2, 2, 1]], #cf_span[[2, 1, 1, 1, 2]], #cf_span[[2, 1, 1]]。它们的代价分别为 #cf_span[4], #cf_span[4], #cf_span[1]。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[2 ≤ n ≤ 105], #cf_span[2 ≤ k ≤ min (n, 20)]) —— 数组的长度和你需要将数组划分成的子段数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ n]) —— 数组的元素。\n\n## Output\n\n请输出一个整数：所得子段的最小可能总代价。\n\n[samples]\n\n## Note\n\n在第一个例子中，最优方案是将序列划分为以下三个子段：#cf_span[[1]], #cf_span[[1, 3]], #cf_span[[3, 3, 2, 1]]。它们的代价分别为 #cf_span[0], #cf_span[0] 和 #cf_span[1]，因此答案为 #cf_span[1]。在第二个例子中，最优方案是将序列划分为两个相等的半部分。每半部分的代价为 #cf_span[4]。在第三个例子中，最优方案是将序列按以下方式划分：#cf_span[[1, 2, 2, 2, 1]], #cf_span[[2, 1, 1, 1, 2]], #cf_span[[2, 1, 1]]。它们的代价分别为 #cf_span[4], #cf_span[4], #cf_span[1]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 10^5 $, $ 2 \\leq k \\leq \\min(n, 20) $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ 1 \\leq a_i \\leq n $.  \n\nFor a subsegment $ A[i:j] = (a_i, a_{i+1}, \\dots, a_j) $, define its **cost** as:  \n$$\n\\text{cost}(i,j) = \\sum_{x=1}^n \\binom{f_x}{2}, \\quad \\text{where } f_x = \\text{frequency of } x \\text{ in } A[i:j].\n$$\n\nA **partition** of $ A $ into $ k $ non-empty, non-intersecting subsegments is a sequence of indices $ 1 = i_0 < i_1 < \\dots < i_k = n+1 $, such that the subsegments are $ A[i_0:i_1-1], A[i_1:i_2-1], \\dots, A[i_{k-1}:i_k-1] $.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 10^5 $  \n2. $ 2 \\leq k \\leq \\min(n, 20) $  \n3. $ 1 \\leq a_i \\leq n $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nFind the minimum total cost over all partitions of $ A $ into exactly $ k $ non-empty contiguous subsegments:  \n$$\n\\min_{1 = i_0 < i_1 < \\dots < i_k = n+1} \\sum_{p=0}^{k-1} \\text{cost}(i_p, i_{p+1} - 1)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF868F","tags":["divide and conquer","dp"],"sample_group":[["7 3\n1 1 3 3 3 2 1","1"],["10 2\n1 2 1 2 1 2 1 2 1 2","8"],["13 3\n1 2 2 2 1 2 1 1 1 2 2 1 1","9"]],"created_at":"2026-03-03 11:00:39"}}