RainAir
My OI Blog
RainAir
HDU 3480 Division

题目链接

题意

有长度为 n 的序列,定义一个集合的代价是$(MAX-MIN)^2$,要求你找出 m 个集合,在满足下面图片的限制的情况下,使得总代价最小。
https://blog.aor.sd.cn/wp-content/uploads/2019/07/3dd1058b5d51c7f6e78982cdf3fbbd51.jpg
多组数据,每组数据 $n \leq 10^4,m \leq 5 \times 10^3$,保证答案在 int 范围内。

题解

观察题目 发现让你选取 M 个集合使得代价最小。
首先一个观察是,取得代价最小的方案一定是按照排序后按顺序取的,并且这些集合两两不交。
然后我们考虑排序后进行 dp:记前 i 段选了 j 个数的最小代价是 $f_{i,j}$,暴力转移就是枚举最后选择的一段区间,暴力转移方程:
$$f_{i,j} = min \{f_{i-1,k} + (a_i – a_{k+1})^2 \}$$
这样复杂度是 $O(n^2m)$ 显然过不去。于是我们来考虑进行斜率优化。
首先发现当前转移只与第二维上一次的状态有关,可以考虑滚动数组,即记 $g = f_{i-1}$,那么我们化简递推式,可以得到
$$f_{i} = min\{g_{k}+(a_i-a_{k+1})^2\}$$
套路地设如果 $j < k$ 且从 $j$ 转移更优,则有式子:
$$g_{j} +(a_i – a_{j+1})^2 < g_k + (a_i – a_{k+1})^2$$
化简一下:
$g_{j} +(a_i – a_{j+1})^2 < g_k + (a_i – a_{k+1})^2$
$\Rightarrow g_j+a_{j+1}^2-2a_ia_{j+1} < g_k + a_{k+1}^2 – 2a_ia_{k+1}$
$\Rightarrow g_j+a_{j+1}^2 – g_k-a_{k+1}^2 < 2a_i(a_{j+1}-a_{k+1})$
不妨令 $F_i = g_i-a_{i+1}^2$
$\Rightarrow F_j-F_k < 2a_i(a_{j+1}-a_{k+1})$
$\Rightarrow \frac{F_j-F_k}{a_{j+1}-a_{k+1}} > 2a_i$
当 $j$ 不比 $k$ 优时,满足 $\frac{F_j-F_k}{a_{j+1}-a_{k+1}} \leq 2a_i$,也可以写成 $\frac{F_k-F_j}{a_{k+1}-a_{j+1}} \leq 2a_i$。
然后直接上斜率优化就好了。具体见代码。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/628
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

HDU 3480 Division
题目链接 题意 有长度为 n 的序列,定义一个集合的代价是$(MAX-MIN)^2$,要求你找出 m 个集合,在满足下面图片的限制的情况下,使得总代价最小。 多组数据,每组数据 $n \leq 10^4,m \…
扫描二维码继续阅读
2019-07-06
标签
近期评论