[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)\) 就可以通过本题了。