danihao123's Blog

在紧张刺激的等待之后终于肝掉了这道题……

本题的DP方程长成这样（其中$a$指$v$的某个满足距离限制的祖先，$d_v$指$v$到根的路径长）：

$$f_v = min(f_a + p_v(d_v - d_a) + q_v)$$

化简之后发现：

$$f_v = q_v + p_v d_v + min(f_a - p_v d_a)$$

利用$min$中那一块很容易发现是截距式……但是问题在于，我们的转移来源是树上的连续一段祖先，怎样维护他们的凸包？

答案很狂暴啊……用树链剖分套上向量集那题的线段树套凸包，然后完了……

（注意一点细节：本题因为数据范围过大，故可能存在两个向量叉乘爆long long，所以在求凸包时如果直接用叉积判断是否需要删点会炸掉，建议用斜率判断）

代码：

emmm做了一下这道神题……（我可能是少有的用动态凸包苟的？）

首先DP方程长这样：

$$f_i = max(f_{i - 1}, f_j\cdot\frac{A_iR_j+B_i}{A_jR_j+B_j})$$

然后这个方程炒鸡复杂……首先$f_{i - 1}$不要管了，然后设$a_i = \frac{f_i}{A_iR_i + B_i}$。在xjb推了一番之后我们终于得到了截距式……

$$-a_j R_j \frac{A_i}{B_i} + \frac{f_i}{B_i} = a_j$$

但是这玩意太毒瘤了……斜率不可能单调的，这还好，在凸壳上二分/三分一下即可。但问题在于，横坐标也不单调……

这个时候就需要动态维护凸包了（其实是我不会CDQ），我直接把我向量集那题的二进制分组线段树搬了过来……（逃

代码：

又做了一道适合我这种沙茶做的题qwq

考虑方差，它满足这个式子：

$$Var(X) = E[X^2] - (E[X])^2$$

对于这个题展开，发现后半部分是一个常量（$(\frac{s_n}{m})^2$）。最小化的就是前半部分，前半部分相当于要求你求一个序列划分，使得各部分平方和的平均值最小。这个值乘上$m^2$之后就变成了各部分平方和乘上$m$。

然后就很简单了……DP方程化简之后是这样的：

$$f_{t, i} = ms_i^2 + max(f_{t - 1, j} + ms_j^2 - 2ms_i s_j)$$

求截距式形式，得：

$$2ms_i s_j + d_i = f_j + ms_j^2$$

然后用类似于上上题的方法搞就行。还有我想想啥时候补一下斜率优化的tutorial……

代码：

又做了一个简单的斜率优化题TAT

首先，设$f_i$表示最后一个放塔的点事$i$时的最优解，那么将原方程化简得：

$$f_i = a_i + \frac{i^2 - i}{2} + max(-ij + \frac{j^2 + j}{2} + f_j)$$

然后求直线形式，得到：

$$ij + d_i = f_j + \frac{j^2 + j}{2}$$

用类似于玩具装箱（上一篇题解）的方式搞一搞即可。

代码：

很久之前是学过并写过斜率优化的……但是很快就忘了。现在感觉自己理解了，感觉是真的懂了……抽空写篇文章解释一下吧……

先单独说这一个题。将DP方程完全展开，并且设$P_i = S_i + i$，$c = L + 1$，可得：

$$f_i = c^2 + P_i^2 - 2P_i c + max(P_j^2 + 2P_j c + f_j - 2P_i P_j)$$

然后$c^2 + P_i^2 - 2P_i c$这部分是常数项不需要管了，我们就想想max里面那些（姑且设之为$d_i$）咋整好了。

设$d_i = P_j^2 + 2P_j c + f_j - 2P_i P_j$，稍作移项，得：

$$2P_i P_j + d_i = P_j^2 + 2P_j c + f_j$$

于是乎，$d_i$可以看做斜率为$2P_i$的直线过点$(P_j, P_j^2 + 2P_j c + f_j)$得到的截距。而那些点我们之前都知道了，问题就变成了已知斜率，求过某点集中的点的最大截距。

想象一个固定斜率的直线从下往上扫，那么碰到的第一个点就是最优解。首先这个点一定在下凸壳上，其次下凸壳上这点两侧的线段的斜率肯定一个比$2P_i$大另一个比它小。并且最好的一点是这个斜率还是单调的，那么分界点一定是单调递增的。

代码：