[CF868-F] Yet Another Minimization Problem

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

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注