[理解]斜率优化DP

[理解]斜率优化DP

单调队列优化DP

对于f[i] = min{ f[j] } + a[i] 型使用

整理归纳单调队列的定义：1、维护区间最值； 2、去除冗杂状态； 3、保持队列单调（最大值是单调递减序列，最小值是单调递增序列）； 4、最优选择在队首。 整理归纳单调队列的使用方法：1、维护队首； 2、在队尾插入（每插入一个就要从队尾开始往前去除冗杂状态） ； 3、取出需要的最优解（队列头的值即是）,借助最优解，得到目前所求的最优解（通常此处插入DP方程）。单调队列的原理：在处理f[i]时，去除冗杂、多余的状态，使得每个状态在队列中只会出现一次；同时维护一个能瞬间得出最优解的队列，减少重新访问的时间；在取得自己所需的值后，为后续的求解做好准备。

斜率优化DP

对于 f[i] = min{ f[j] + 一坨  + (含i的) * (含j的) + 一坨 } 型使用

类似于单调队列

我们队列里存斜率,如果当前肯定不是最优,就弹开

如果当前不符合规矩,也弹开

看看例题理解

题目大意：  给出一个有N (1<= N <=400000)个正数的序列，要求把序列分成若干组（可以打乱顺序），每组的元素个数不能小于T (1 < T <= N)。每一组的代价是每个元素与最小元素的差之和，总代价是每个组的代价之和，求总代价的最小值。

样例输入包含：  第一行 N  第二行 N个数，如题意

样例输出包含：  第一行 最小的总代价

先排序,再DP

很容易得出

f[i] = min{f[j] + sum(j+1,i) -a[j+1]}

转换为前缀和

f[i] = min{f[j] + sum[i] -sum[j] - a[j+1] * ( i - j )}

整理为 f[i] = min{ f[j] + 一坨  + (含i的) * (含j的) + 一坨 }

f[i] =min{f[j] - ( sum[j] - a[j+1] * j )  -  i * a[j+1] + sum[i]}

我们令 f[j] - ( sum[j] - a[j+1] * j ) = y

i = k , a[j+1] = x , f[i] = b

m = sum[i] 为常数先不计

于是 b = y - kx   , y= kx + b

当枚举到i时,k为定值,函数与y轴的交点即为f[i]

同理,我们在i更大时,可以画出更多个点

用一个斜率为i的去靠,第一个靠到的就是最优的

同时,i是增大的,也就是说,去靠的那个线越来越陡

当陡到一定程度时,第一个交点就变了

而越在前面的就越没用可能,于是可以丢掉

于是我们保留当前最优的,与将来可能最优的

在i变大时

我们发现i的斜率比A1 A2大,于是舍弃 A1

如果进来一个A3 , 破坏了规则(相当与单调队列来了一个比前面都小的,就要从队尾弹出)

变换到符合规则,也就是

于是大致思路

新来一个点如果当前点与前一个点的斜率

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。