zcmimi's blog

arrow_back斜率优化共7篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f_i为前i个任务的费用,t_i为前i个任务时间的总和,w_i为前i个任务费用的总和

f_i=\min_{j=0}^{i-1}(f_j+s\times(w_n-w_j)+t_i\times(w_i-w_j))

设任意0\le j<k<ij转移比从k转移优,那么

f_j+s\times(w_n-w_j)+t_i\times(w_i-w_j) \le f_k+s\times(w_n-w_k)+t_i\times(w_i-w_k) \\ t_i(w_k-w_j)\le f_k-f_j+s(w_j-w_k) \\ t_i\le \frac{f_k-f_j+s(w_j-w_k)}{w_k-w_j} \\ t_i+s\le \frac{f_k-f_j}{w_k-w_j}

维护个下凸壳就可以了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f_i表示前i块土地

f_i=\min_{j=1}^{i-1}(f_j+maxw[j-1][i]\times maxh[j-1][i])

这样的话怎么想都没有办法优化

我们发现,如果一块土地被另一块土地所包含(即长和宽都比另一块土地小),

那么只需购买那另一块土地即可,于是我们可以据此筛掉其他的土地,

只剩下一些长度递减,宽度递增的土地

那么:

f_i=\min_{j=1}^{i-1}(f_j+l[j+1]\times w[i])

设任意0\le j<k<i,若从j转移比从k转移优,那么

f_j+l[j+1]\times w[i]\le f_k+l[k+1]\times w[i] \\ w[i](l[j+1]-l[k+1])\le f_k-f_j \\ w[i]\le \frac{f_k-f_j}{l[j+1]-l[k+1]}

维护一个下凸壳就完事了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

斜率优化入门题

f_i表示前i件玩具的制作费用

f_i=\min_{j=1}^{i-1}(f[j]+(i-j-1+s_i-s_j-L)^2)

显然\Theta(n^2)不能满足要求

a_i=s_i+i,b[i]=s_i+i+L+1

(都只与i有关)

那么 f_i=\min_{j=1}^{i-1}(f_j+(a_i-b_j)^2) \\\text{展开得}\\ f_i=f_j+{a_i}^2-2a_ib_j+{b_j}^2 \\\text{移项得}\\ 2a_ib_j+f_i-{a_i}^2=f_j+{b_j}^2

x=b_j,y=f_j+{b_j}^2 y=2a_ix+(f_i-{a_i}^2)

可以看成一条斜率为2a_i的直线

f_i含义转化为当上述直线经过点(x,y)(b_j,f_j+{b_j}^2)时,直线在y轴的截距上加上{a_i}^2

题目就是要找这个最小的截距

我们可以将这条直线从下往上平移,直到经过第一个点

这样的话我们可以维护一个下凸壳

求的过程大概是这样:

https://www.desmos.com/calculator/mqsdvzuaee

那么如何维护这样一个下凸壳呢?

可以发现凸壳中的相邻两点的斜率是递增的

我们可以用单调队列维护

那么查询呢?

我们可以发现:

如果当前直线经过的点左边的斜率<当前斜率<右边的斜率,

那么这个点就是最优的。

我们可以按照下面的方案实现:

设队头为h,队尾为t,队列数组为q,s(i,j)为直线ij的斜率

  1. while(s(q_h,q_{h+1})<2a_i)++h;
  2. 当前队头的点最优,用这个点计算出f_i
  3. while(s(q_{t-1},q_t)>s(q_{t-1},i))--t;
  4. 队尾插入点i

对于3操作的解释:

假设当前插入的是红点,那么绿点明显在凸包内,要删除掉

avatar
zcmimi
2019-12-21 19:47:00
查看原题

点击跳转

f_i表示前i个拆分后最大战斗力和

f_i=\max_{j=1}^{i-1}(f_j+a(s_i-s_j)^2+b(s_i-s_j)+c)

这个很明显是斜率优化式子

设任意0\le j<k < i,若从j转移到i优于从k转移,那么:

f_j+a(s_i-s_j)^2+b(s_i-s_j)+c\ge f_k+a(s_i-s_k)^2+b(s_i-s_k)+c \\ 2as_i\le\frac{(f_k+a{s_k}^2-bs_k)-(f_j+a{s_j}^2-bs_j)}{s_k-s_j}

维护个下凸壳就完事了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f(i,k)表示将前i个分k次的分数

我们可以dpk次就可以了

f_i为前i个,g_i为上一次dp的结果

f_i=\max_{j=1}^{i-1}(g_j+s_j\times(s_i-s_j))

取任意0\le k<j <i且从j转移比从k更优,那么

g_j+s_j\times(s_i-s_j)\ge g_k+s_k\times(s_i-s_k) 展开得

g_j+s_is_j-{s_j}^2\ge g_k+s_is_k-{s_k}^2 移项得 s_i(s_j-s_k) \ge {s_j}^2-{s_k}^2+g_k-g_j 整理得 s_i\ge \frac{({s_j}^2-g_j)-({s_k}^2-g_k)}{s_j-s_k}

注意s_j-s_k有可能为0,要特判

因为要求的是最大值,所以我们维护一个上凸壳就可以了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f_i为前i个任务的费用,t_i为前i个任务时间的总和,w_i为前i个任务费用的总和

f_i=\min_{j=0}^{i-1}(f_j+s\times(w_n-w_j)+t_i\times(w_i-w_j))

设任意0\le j<k<ij转移比从k转移优,那么

f_j+s\times(w_n-w_j)+t_i\times(w_i-w_j) \le f_k+s\times(w_n-w_k)+t_i\times(w_i-w_k) \\ t_i(w_k-w_j)\le f_k-f_j+s(w_j-w_k) \\ t_i\le \frac{f_k-f_j+s(w_j-w_k)}{w_k-w_j}

维护了个下凸壳交了上去,结果听取\color{red}\text{WA}声一片

仔细看了看|T_i|\le 2^8

这也就意味着我们每次截取的直线的斜率不再单调递增,单调队列不能再满足需要

为了保证决策状态的有序性,我们还是选择用一个单调栈维护下凸包。

因为决策集合已经有序,对于任意直线,我们只用在队列中二分出使截距最小的交点

由于出题人十分毒瘤,我们要把斜率大小的判断从相除改成十字相乘

1/1
Search
search