概述

斜率优化(Convex Hull Trick)

将状态转移方程转化为 $d(i) = k(i)x(j) + y(j) (+ c(i))$ 的形式

其中$x(j),y(j)$都是可以在常数时间内由$j$唯一确定的二元组
$k(i)$ 由i确定,$c(i)$由i确定,可以忽略

我们的目标是$min\;P = kx + y$,其中$P = d(i)$
即使直线 $y = -kx + P$ 纵截距最小

想象一条直线自下而上所碰到的第一个点即为答案,显然这些点在凸壳
所以我们可以维护一个 $(x(j),y(j))$ 组成的凸壳
可以根据 x 和 k 的性质来维护

对于$max\; P$则想象一条直线自上而下所碰到的第一个点即为答案

分类

x与k同时单调

一般默认x单调递增

x与k单调性不一致,用单调栈维护一个斜率单调递增的凸壳,保证栈顶的斜率恰大于等于当前斜率k,每次从栈顶更新

x与k单调性一致,则用一个单调队列维护,在队尾维护一个斜率单调递增的凸壳,用当前斜率k维护队首,保证队首的斜率恰大于等于k,每次从队首更新

x单调 k不单调

一般默认x单调递增

用单调栈维护一个用单调栈维护一个斜率单调递增的凸壳
二分出第一个斜率大于等于k的位置,并更新

x不单调k单调

Splay维护凸壳,每次决策后可以删掉一些点

或者cdp分治

x与k都不单调

Splay维护凸壳,正常决策,不能删点

或者cdp分治

题目

hdu3507

将一个序列C分为若干连续部分
每部分消耗为 $(\sum C_i)^2 + M$

$d[i] = min(d[j] + (sum_i - sum_j)^2 + M)$
$d[i] = d[j] + sum^2_j - 2sum_isum_j + sum^2_i + M$
令$x(j) = sum_j,y(j) = d[j] + sum^2_j,k(i) = 2sum_i$
$min P = -kx + y$
$y = kx + P$
其中x与k都单调递增,可以用单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LL up(int k,int j)
{
return d[j] + P(sum[j]) - d[k] - P(sum[k]);
}

LL down(int k,int j)
{
return (sum[j] - sum[k]);
}

void solve()
{
l = r = 0;
q[r++] = d[0] = 0;
F(i,1,n)
{
while(l+1 < r && up(q[l],q[l+1]) < 2*sum[i]*down(q[l],q[l+1])) ++l;
d[i] = d[q[l]] + P(sum[i] - sum[q[l]]) + m;
while(l+1 < r && up(q[r-2],q[r-1])*down(q[r-1],i) >= up(q[r-1],i)*down(q[r-2],q[r-1])) --r;
q[r++] = i;
}
}

hdu 5956

上面一题的树上版本,输出的是所有$d[i]$的最大值
我们考虑两种做法

树分治

若当前节点为分治部分的根节点,则直接用其更新所有子树的节点
若当前节点不为分治部分的根节点,则先递归更新根节点不含当前节点部分的所有子树
然后将根节点到当前节点的这条链维护一个单调栈,并用其二分更新当前节点的所有子树节点

复杂度 $O(nlog^2n)$

可持久化单调栈

维护一个单调栈,记录更新父亲节点后单调栈位置
每次回溯时可以$O(1)$恢复单调栈之前的状态

复杂度 $O(nlogn)$

BZOJ 1492 货币兑换Cash

刚开始有S元,有N天,每天有A、B两种金券,$A_x,B_x,Rate_x$分别表示金券A、B价格,兑换比例
每天可以选择

  • 卖出金券:顾客选择一个[0,100]以内的实数作为比例OP%,可以卖出OP%的A劵和OP%的B劵,获得对应价格的人民币
  • 买入金券:顾客支付IP元人民币,交易所按每天的兑换比例兑换给用户对应价值的A、B劵
    用户每天可以进行多次操作,问第N天最多能获得多少钱

显然最大获利即有一天将全部的金券卖出
设$d[i]$为第i天的最大获利

$d[0] = S$
$d[i] = max(d[i-1],a[i]x(j)+b[i]y(j))$

$x(j),y(j)$ 表示第j天将最大获利f[j]都兑换为A劵和B劵的数量

$y(j) = f[j]/(a[j]rate[j] + b[j])$
$x(j) = y(j)
rate[j]$

目标$max P = ax + by$
$y = -a/bx + P/b$

斜率$k = -a/b$ 与 x 均不满足单调性
要用Splay维护一个凸包,然而我不会
所以写了简单易懂的cdq分治

我们先将所有点按斜率从大到小排序

分治时,前一半已更新完成,满足x单调递增
此时维护一个斜率单调递减的凸壳

更新后一半时,后一半斜率单调递减
在队首维护保证队首的斜率恰大于等于当前斜率k

然后更新完成后将两部分按x从小到大归并排序

cf-351 e

将序列分为k部分,在某一部分中,选取某个元素的概率为$p_i = \frac{t_i}{\sum t_j}$
求一种分割方式使选取全部元素时取的次数期望最小,输出期望

取某个球的期望为$1/p_i$

$d_{i,j} = min(d_{k,j-1} + cost_{k+1,i})$

其中$cost(k,i) = (sum_i - sum_k)\sum_{j = k+1}^i\frac{1}{t_j}$

然而这样表示很难化成上述的斜率式子,我们把式子修改一下
$\begin{align}
cost(k,i)& = \sum_{j = k+1}^i \frac{sum_i}{t_j} - sum_{i-1}\sum_{j = k}^i \frac{1}{t_j} \\
& = p_i - p_k + sum_k(rev_i - rev_k) \\
& p_i = \sum \frac{sum_i}{t_i} \;\; rev_i = \sum 1/t_i
\end{align}
$

$\frac{d_{j-1,j} - d_{j-1,k} + p_k - p_j + sum_jrev_j - sum_krev_k}{sum_j - sum_k} < rev_i$

参考