[CF868-F] Yet Another Minimization Problem

时间限制：1000MS 内存限制：262144KB

难度：$6.0$

• 题目描述

有 $n$ 个正整数构成序列 $a$ ，定义一个区间 $[l, r]$ 的代价为 满足 $l \leq i, j \leq r$ 并使得 $a_i=a_j$ 的无序对 $[i, j]$ 的数量。

现要把 $a$ 分成 $k$ 个互不相交且不为空的连续的区间，求出在所有分法中，分出区间的最小代价和是多少。

• 输入格式

第一行，两个正整数 $n, k$ 。

第二行，序列 $a$ ，共 $n$ 个元素，用一个空格隔开。

• 输出格式

一个整数，表示在所有分法中，分出区间的最小代价和。

• 样例输入

• 样例输出

• 样例说明

一种可能的分法为 $[1], [1, 3], [3, 3, 2, 1]$ 。

第一个区间的代价为 $0$ ，第二个区间的代价为 $0$ ，第三个区间的代价为 $1$ ，最小代价和为 $1$ 。

（其他样例见原题

• 数据范围

对于 $10\%$ 的数据，$2 \leq n \leq 20$ 。

对于 $40\%$ 的数据，$2 \leq n \leq 1000$ 。

对于 $100\%$ 的数据，$2 \leq n \leq 10^5$ ，$2 \leq k \leq min\{20,n\}$ 。

保证 $1 \leq a_i \leq n$ 。

 

 

 

$Source$: CF868-F

---

 

 

 

设 $f_{i, j}$ 为做到第 $i$ 个数，$1$ ~ $i$ 中分了 $j$ 段的最小代价。

所以 $f_{i,j}=\min\limits_{k=1}^{i-1}\{f_{k,j-1}+w_{k,i}\}$ ， $w_{k, i}$ 表示 $[k+1, i]$ （注意范围） 为一段的代价（两两相同的数的无序对对数），发现 $j$ 这一维可以直接滚动掉（不滚动其实也没什么www）。

就变成了 $g_i=\min\limits_{k=1}^{i-1}\{f_k+w_{k,i}\}$ ，时间复杂度 $O(n^2k)$ 无法通过本题。

 

 

 

 

---

（注：记一段区间内相同的数的无序对对数可以方便地开一个桶，增加一个元素 $a$ 表示 w+=cnt[a]++; ，删除一个元素 $a$ 表示 w-=--cnt[a]; ，因为相同元素 $a$ 的无序对对数为 $C_{cnt_a}^2=\frac{cnt_a(cnt_a-1)}{2} = 1+2+\cdots+(cnt_a-1)$ 。

（要求 $w_{k, i}$ ，只需要把 $1$ ~ $i$ 的所有元素先加到一个变量 $w$ 中，然后依次删除 $1, 2, \cdots , i$ ，删除第 $k$ 个元素后 $w$ 的值就为 $w_{k, i}$ 。

继续优化，同时注意到决策的单调性。即对于 $a<b<c<d$，如果 $c$ 从 $b$ 转移过来比从 $a$ 转移过来更优，那么 $d$ 从 $b$ 转移过来也比从 $a$ 转移过来更优。即若满足 ${{f_b} + {w_{b,c}} \le {f_a} + {w_{a,c}}}$ 那么一定满足 ${{f_b} + {w_{b,d}} \le {f_a} + {w_{a,d}}}$ 。注意到只要满足 $w_{b,d}-w_{b,c} \leq w_{a,d}-w_{a,c}$ 那么上面的结论一定成立。发现这个条件其实就是四边形不等式 $w_{a,c}+w_{b,d} \leq w_{a,d}+w_{b,c}$ 。

对于本题，假设颜色 $a$ 分别在 $(a,b]$ 、 $(b,c]$ 、 $(c,d]$ 中的数量为 $x ,y, z$ 。那么就有如下关系（倒推）：

$\begin{array}{c} {w_{a,c}} + {w_{b,d}} \le {w_{a,d}} + {w_{b,c}}\\ C_{x + y}^2 + C_{y + z}^2 \le C_{x + y + z}^2 + C_y^2\\ \left( {x + y} \right)\left( {x + y – 1} \right) + \left( {y + z} \right)\left( {y + z – 1} \right) \le \left( {x + y + z} \right)\left( {x + y + z – 1} \right) + \left( {y + z} \right)\left( {y + z – 1} \right)\\ 0 \le xz \end{array}$

$0 \leq xz$ 那是废话一定正确，也就证明了决策的单调性。

同时还发现此题的 $w_{k,i}$ 无法对于指定的 $k, i$ 在 $O(1)$ 时间内求出，所以无法使用决策二分栈等方法，考虑操作是单调并且离线，所以使用分治。

求解区间：$|\gets$ 之前处理的信息 $\to|$ $l\frac{\qquad\qquad\qquad\downarrow^{mid}\qquad\qquad\qquad}{}r$

决策区间：$kl\frac{\qquad\qquad\qquad\qquad\qquad\qquad\downarrow^{k}\qquad\qquad\qquad}{}kr$

这里之前处理的信息主要指 $w$ 和 $cnt$ 数组。

当前求解的区间为 $[l, r]$ ，而最优决策可能在的区间为 $[kl, kr]$ 。则对于 $mid=\lfloor\frac{l+r}{2}\rfloor$ ，需要暴力找出 $[kl, min\{mid-1, kr\}]$ 中最优的转移点 $k$ 。

注意，之前预处理的信息 $w$ 表示 $[kl, l)$ 这一区间的代价，所以在寻找最优转移点的时候按照朴素DP的方法快速计算出所需的 $w$ 。记得算完后要复原。

要处理 $[l, mid)$ 时，它的决策区间为 $[kl, k]$ 。因为 $w$ 原本就表示 $[kl, l]$ 这一区间的代价，所以不需要加任何处理即可直接递归进这个子区间。

值得注意的是，处理 $(mid, r]$ 时，它的决策区间为 $[k, kr]$ 。对照上面的简图发现有 $[l, k)$ 这一段信息还未处理，所以先处理出它的信息，然后就可以递归进这个子区间了。记得回溯的时候复原。

这样分治的优秀复杂度 $O(nklogn)$ 就可以通过本题了。