例题：薯片小明现在体重\(W\)公斤，减肥将会持续\(n\)天。第\(i\)天如果不吃薯片体重将会减少\(A\)公斤，吃了体重会增加\(D_i\)公斤。但是不吃薯片实在是很难受，这个难受情况用压力值来描述。一开始压力值为\(0\)，每一天不吃薯片压力值将会增加\(1\)，吃了薯片压力值又会变回

斜率优化\(y=kx+b\)形式维护队列，询问不单调则二分决策点。SlopeTrick如果决策函数满足以下条件：连续凸包，每一段斜率为整数凸包上断点之间的一次函数斜率总和为\(\mathcalO(n)\)级别则称这个函数满足性质\(T\)，且如果\(f,h\)都满足性质\(T\)，则\(f+h\)也满足性质

静态维护凸包动态维护凸包Splay平衡树维护每个点向左、向右的线段的斜率\(lp,rp\)（初始为\(INF\)和\(-INF\)方便插入）插入一个点时，先加入Splay，再向左右找到最接近的，可与新点形成新的凸包的点，把中间点删掉，更新\(lp,rp\)即可具体实现：codecdq分治题目P4027[NOI2007]货币兑换

完整准确地理解FlushHu的题解。0x00初步分析我们发现对于矩形\(i,j\)满足\(h_i\leqh_j,w_i\leqw_j\)，那么选\(j\)的时候一定可以并购\(i\)，因此将\(i\)删去。将剩下的矩形按照\(h\)从大到小排序，此时\(w\)从小到大。因为如果合并的不是一段连续区间，那么中间未被

现在已知一堆点\((t_i,a_i)\)。要求所有点对组成直线的Max/min斜率。（绝对值）Max我们考虑找一道类似的题目：P11021。这道题求的是max，支持修改。此时结论为：答案来自于所有\(t_i\)相邻的点。如此我们直接set维护修改就做完了。考虑正确性。对于\((i,i+1)\)，我们想找到更优

20241012模拟赛A.组合一眼转化成前缀相减的形式，然后注意到\(a,b,c\le2000\)，于是\(O(n^2)\)预处理就做完了。B.原神先考虑暴力一点的想法。考虑枚举最靠右的瓶子\(i\)，再枚举选的瓶子的个数\(k\)，那么这时无论在前面选了哪些数，答案都会异或上\(\sum_{j=i-k+1}^{i}a_j\)

首先看到有\(i,j\)无法分离的项的\(\rmDP\)一般就是斜率优化，像\((s_i-s_j)^2\)之类的。首先将转移方程式写成\(b_i=y_j-k_ix_j\)的形式，拍到坐标系上。那么等价于用斜率为\(k_i\)的直线去切点，第一个切到的点是哪个，即截距最小/最大。显然切到的点在凸包上，即找到

B平面上有\(n\)个点以及\(k\)条未知的平行线，每个点都分属一条线，每条线都有至少\(2\)点。给出一种方案。\(n\le4e4,k\le50\)。每个点分属一条线的条件非常重要。考虑利用鸽巢原理。考虑取出\(k+1\)个没有两对点同斜率的点，那么，至少有两个点在一条线上，那么就可以确定斜

1.概念速度角度：在物理学中，速度是描述物体位置随时间变化快慢的量。假设我们有一个函数f(t1)表示物体在时间t1的位置，f(t2)表示物体在时间t2的位置，那么在t1到t2时间段内，物体移动的距离为f(t2)-f(t1)，平均速度为：                             

SS241009C.蛋糕（cake）题意你有\(n\)个数字，有两种操作。删除最左边的数字，代价为数字大小。（吃左边）令\(>0\)的所有数字大小减\(1\)，代价为\(>0\)的最大的数字的初始值。（吃底下）求删完所有数字的最小代价。思路据搜索引擎，凹包不具有斜率单调性质，因此题解说的凹包应为凸包

斜率优化初探：以[HNOI2008]玩具装箱为例记\(f[i]\)表示装好前\(i\)个的最小花费。容易写出转移：\[f[i]=\min_{j\lti}\[f[j]+(s[i]-s[j]-1-L)^2]\]直接转移是\(O(n^2)\)的，我们考虑斜率优化。斜率优化的过程（一）问题转化成了求最小截距。我们把\(min\)

斜率优化DP在单调队列优化过程中，转移方程被拆成了两部分，第一部分仅与\(j\)有关，而另一部分仅与\(i\)有关，因此我们可以利用单调队列仅维护与\(j\)有关的部分，实现问题的快速求解。但仍然有很多转移方程，\(i\)和\(j\)是紧密相关的，这个时候单调队列优化就不适用了，例如如下转

二分答案转化为判定，这样我们就只关心最大的和是否大于0，而不关心除以区间长度的干扰了赛场上阴差阳错地写对了斜率优化，但是想不明白原理，几经周折查找资料，终于明白了：弹出队头决策的确会导致当前解未必最优，但一定不会干扰全局最优解；如果需要查找当前最优解，则需要二分下凸壳在DP的

斜率优化模板题，有三倍经验，难度逐渐递增，建议从前做到后。P2365任务安排，P10979任务安排2，P5785[SDOI2012]任务安排。（但是我这种做法P10979和P5785没有区别。思路：设\(f_i\)表示第\(i\)个任务加工后所需的最小总费用，那么就有转移式。\[f_i=\displaystyle\min_{j=0}^{

AtCoder比较遗憾，E题用了太多时间了，没做出来。当时看到有平方感觉难道是斜率优化之类的？这下猜对了。拜谢WA90。不过官解好像没用斜率优化？不会。设\(f_{i,j}\)表示前\(i\)个物品一共用了\(j\)的体积。直接暴力做是三次方的。当加入一个体积为\(w\)，价值为\(v\)的物品

        下表为中国内地某年各地区税收Y与国内生产总值的GDP的统计资料。地区YGDP 北京1435.79353.3 天津438.45050.4 河北618.313709.5 山西430.55733.4 内蒙古347.96091.1 辽宁815.711023.5 吉林237.45284.7 黑龙江3357065 上海1975.512188.9 江苏1894.82

任务安排1~3：模版。用到一个著名的思想：费用提前计算。暴力维数高的原因是不能较快的知道前面分了几批但是一旦分了一批，对后面都会有\(S\)的时间叠加所以不妨设\(f_i\)表示已知会花费的时间min，\(f_i=\min_{j=1}^{i-1}f_j+(SC_i-SC_j)\cdotST_i+S\cdot(SC_n-SC_j)\)

看我之前写的狗屎：https://www.becoder.com.cn/article/11836。当时根本就不懂斜率优化是什么。今天真的懂了，来写总结。1问题转化对于一类dp方程式：\(f(i)=\min\{f(j)+A(j)*g(i)+B(j)+t(i)\}\)。可以用斜率优化。设\(b=f(i)-t(i)\)。把当前dp转移当成是一条斜率

传送门给定一棵树，带边权。\(1\)的代价可以使某边权\(\pm1\)。求最小代价使从根到叶子距离都相等。\(n\le3\times10^5,w_e\le10^9\)。\(f_u(x)\)表示\(u\)的子树内把\(u\)到叶子的距离都变成\(x\)的最小代价。\(F_u(x)\)表示\(u\)的子树内把\(fa[u]\)到叶子

感觉一个比较入门的题目是P2619。你要求的是恰好有\(need\)条白色边的，这个很难表示，因为如果直接跑一遍MST，你不能保证一定选了\(need\)条，有可能白色边“太好了”或者“太坏了”。但是我们发现，如果白色边“越好”，就会尽可能选白色，反之亦然。也就是说如果我们增加一个费用：给所

 给定二维点p(x0,y0)的坐标。找到距离该点L的点，使得连接这些点所形成的线的斜率为M。例子： 输入：p=(2,1)    L=sqrt(2)    M=1输出：3,2    1,0解释：与源的距离为sqrt(2)，并具有所需的斜率m=1。输入：p=(1,0)   

由ryz讲解什么是分治？把一个较大规模的问题分成若干个较小规模的问题。小规模的问题与原问题不同（根号分治）小规模的问题与原问题相同（对数分治）二分就是一种对数分治的方法。操作序列分治cdq分治修改和询问的整体分治也被称为cdq分治。要求：修改对询问具有可加性

斜率优化DP例题任务安排题面\(n\)个任务排成一个序列在一台机器上等待完成（顺序不得改变），这\(N\)个任务被分成若干批，每批包含相邻的若干任务。从零时刻开始，这些任务被分批加工，第\(i\)个任务单独完成所需的时间为\(T_i\)。在每批任务开始前，机器需要启动时间\(S\)，而完成这

在看wqs二分前建议先去看另一篇博客——斜率优化，对凸包等知识点有所了解。介绍wqs二分最初由王钦石在他的2012年国家集训队论文中提出，也叫"带权二分"，或者"dp凸优化"，而从IOI2016的Aliens题目开始，这种方法开始逐步在竞赛圈中有了一定的地位。在国内我们一般称为「wqs二

引言在学数据结构优化dp,单调队列优化dp时都很快就懂了，四边形不等式优化dp看一看也懂了，只有斜率优化理解了一个月还不懂，最后在其他大佬和资料的帮助下成功学懂了，于是争取这篇题解在以后又不会的时候一遍就懂。前置数学知识1.一次函数初中数学知识，见八年级数学课本。2.凸包(