斜率

点A(x1,y1) 点B(x2,y2) k代表斜率,b为常数 y1 - y2 k = ————————— x1 - x2 y1 = k * x1 + b y2 = k * x2 + b y2 = k * x2 + ( y1 - k * x1 ) 若 点A(65,75) 点B(20,20) 75-20 ......

发现别的人都对斜优很熟，就我不是（悲），所以写个小记辅助记忆一下。 1.应用范围 众所周知，单调队列优化 dp 可以解决形如 \(dp_i=val_i-val'_j\) 的问题 那么如果再加一个 \(val''_ival'''j\) 呢 这就要用斜率优化了。 2.方法 这东西非常灵活，所以直接上题目 ......

原题链接：斜率。 题意 在一个平面直角坐标系中，给定 \(n\) 个点的横纵坐标，求出哪两个点所构成的连线的斜率最接近 \(\frac{P}{Q}\)。 数据范围：\(n \le 1000000\)。 思路 显然这是一道数学题，不能直接暴力去找答案。 首先我们可以弱化一下题目，求出斜率最接近 \(y ......

[ZJOI2007] 仓库建设 题目描述 L 公司有 \(n\) 个工厂，由高到低分布在一座山上，工厂 \(1\) 在山顶，工厂 \(n\) 在山脚。 由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L 公司的总裁 L 先生接到气象部门的电话，被告知三 ......

题目描述 Zxr960115 is owner of a large farm. He feeds mm cute cats and employs pp feeders. There's a straight road across the farm and nn hills along the ......

终于开始斜率优化了。。洛谷P2365 任务安排 题目描述 nn 个任务排成一个序列在一台机器上等待完成（顺序不得改变），这 nn 个任务被分成若干批，每批包含相邻的若干任务。 从零时刻开始，这些任务被分批加工，第 ii 个任务单独完成所需的时间为 titi​。在每批任务开始前，机器需要启动时间 ss ......

题解 首先，递推关系如下： \(dp[i] = min(dp[i], dp[j] + sumt[i] * (sumc[i] - sumc[j]) + s * (sumc[n] - sumc[j]));\) 显然N太大，无法\(O(n^2)\)算法解决问题。考虑如何优化掉第二个j的循环，发现这个循环是 ......

前言 考试 T2 出题人放了个树上斜率优化 DP，直接被同校 OIER 吊起来锤。 离 NOIP 还有不到一周，赶紧学一点。 引入 斜率 斜率，数学、几何学名词，是表示一条直线（或曲线的切线）关于（横）坐标轴倾斜程度的量。它通常用直线（或曲线的切线）与（横）坐标轴夹角的正切，或两点的纵坐标之差与横坐 ......

使用场景 状态 \(O(n)\)，转移 \(O(n)\)，只涉及 \(i,j\) 两个未知量，\(j\) 的取值范围的左、右端单调，可以把 \(f_i\) 当做截距维护上（max）、下（min）凸包。需要注意的是，它作用不仅仅可以优化 DP，本质是求某些最值，\(\color{red}\text{e ......

这里并不是在详细地介绍斜率优化，只是一些瞎扯，想真正系统学习斜率优化的话请去阅读其他文章。 斜率优化是众多 dp 优化方式中较为常见的一种，让我们不妨回忆一下它的形式： \[dp(i)=\min/\max(a(i)\times b(j)+c(i)+d(j)+C) \]上式中，\(a,b,c,d\) ......

记一下。 形如 \(f_i=\min/\max\{f_j+a_ib_j+c_i+d_j+e\}\) 的式子可以使用斜率优化。 如果斜率有单调性，可以使用单调队列。 如果没有，可以使用李超树或者 cdq 分治。 单调队列暂鸽。 没有单调性，使用李超树。 为方便记录，只讨论 \(f_i=\min\{f_ ......

P4360 [CEOI2004] 锯木厂选址 令 \(f_i\) 表示仅在 \(i\) 位置修建一个锯木厂的最小费用，\(dis_i\) 表示从山脚到 \(i\) 位置的距离，\(sum_i\) 表示从山顶到 \(i\) 位置的木材重量和，可以直接预处理出来。 那么第二个锯木厂修建在位置 \(i\) ......

转移到 \(i\) 时考虑两个转移点 \(j<k\) 中 \(j\) 更优的条件，可以写成 \(\dfrac{a_k-a_j}{b_k-b_j}\) 大于或者小于 \(c_i\) 的形式。 把信息看做二维平面上的点 \((b,a)\)，那么上面的条件实际上就是 \(j\) 与 \(k\) 两点间的斜 ......

斜率优化是一种优化 \(dp\) 的方法，不过在哪之前，我们需要引入一道例题。 点击查看代码 给你一个长度为 $n$ 序列 $A$,你需要把他分成若干段。定义第 $x$ 段的贡献为： $$a \times(\sum_{i=l_x}^{r_x} a_i))^2 +b\times \sum_{i=l_x ......

引入 有时候 我们会遇见一些 dp 式子 \[f_i=\min(f_j+a_i\times b_i)(j\leq i-1) \]这些式子和 \(j\) 没有任何关系 可以前缀处理最小值 \(O(n)\) 快速解决 但是有些式子是这样的 \[f_i=\min(f_j+a_i\times b_j+c_i ......

下面可能会用到一些叫上凸壳鸭下凸壳呀的名词，大家不用弄懂它的概念的说也不用望风而逃（我之前就望风而逃过(*/ω＼*)），凸壳就简单理解成一个凸了一块的一段连线就好了。 斜率优化有些地方不好用代数的语言刻画，比如下凸壳，比如凸包（凸包有的定义就直接写橡皮筋的比喻 233333），以及为什么下凸点/上凸 ......

斜率优化dp 【模板】任务安排 机器上有 n 个需要处理的任务，它们构成了一个序列。这些任务被标号为 1 到 n，因此序列的排列为 1 , 2 , 3 .... n。这 n 个任务被分成若干批，每批包含相邻的若干任务。从时刻 0 开始，这些任务被分批加工，第 i 个任务单独完成所需的时间是 T_i。 ......

其实我很早就学习了斜率优化，觉得这个东西比较套路化，写不写都可以。 今天看到不少网友对其十分热衷，我想还是动手写一篇。 P4655 [CEOI2017] Building Bridges 题意：　有 n 根柱子，第 i 根的高度是 a[i]，你可以选择保留一些，其他的全被拆掉。 拆除第 i 根柱子的 ......

斜率公式一 当直线的倾斜角为α（α≠90°）时，直线的斜率k=tanα。 斜率公式二 当直线不与x轴垂直（倾斜角α≠90°）时，任取直线上两点A(a,b)、B(c,d)，直线斜率k=(d-b)/(c-a)或k=(b-d)/(a-c)。 倾斜角90度，斜率不存在 倾斜角0度，斜率为0 参考 直线倾斜角 ......

众所周知，动态规划推出状态转移方程是很困难的，推出状态转移方程后发现复杂度爆炸是很炸裂的，所以这就是斜率优化存在的意义 降低转移方程的复杂度 在看具体例子之前，我们先大致的介绍一下斜率优化的原理 考虑一个这样的状态转移方程，f[i]=min{f[j]-k[i]*j+s[i]} j<i，f 用于储存/ ......

 ![image](https://img2023.cnblogs.com/blog/2954438/20... ......

# 斜率优化 DP ## 适用情况 适用于求解最优解（最大、最小）问题。 ## 上凸壳与下凸壳  ## 求解步骤 1. 对于任意状态转义方程，设 $A_i$，$B_i$，使状 ......

[例题](https://www.luogu.com.cn/problem/P3195) 考虑朴素做法: $f_i$表示把前$i$个玩具装箱所需的最小费用，$s_i$为$c_i$的前缀和，则有： $$f_i=\min\limits_{j=1}^i(f_{j-1}+(i-j+s_i-s_{j-1}-L ......

~~仍然是算导风格的学习笔记~~ 例题：[[HNOI2008] 玩具装箱](https://www.luogu.com.cn/problem/P3195) P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的 ......

### 前置芝士 单调队列优化 DP ⌈ 写不动数据结构呜呜呜，先来补这个 ⌋ 对于一个 DP，我们想优化祂的 ⌈ 转移 ⌋ 有些题目的可选状态有以下特征 + 需要寻找最值 + 可选状态区间平移 + 存在可以永久去除的多余状态 感性的讲，可行性是一个滑动窗口，状态两两之间都可以 ⌈ 直接比较出优劣 ......

这是等了好久的笔记了。 斜率优化一直是我 OI 中的一个大坑，我刚接触它的时候是在 摆渡车 这题，看到斜率凸包啥的，那时候我才是六年级，十分的不理解，于是一直觉得它十分困难。 暑假终于迎来了转机，NLFS 讲 DP 优化那天顺便讲了下斜率优化，终于大悟，乃写此文章，供复习等用。 先来看一道题： 斜率 ......

# part 1 引入 ### 一.斜率优化的作用 在一个dp中，往往转移一个状态与很多状态相关，每一次转移都扫一遍与它相关的状态浪费了很多时间。但总有一些状态无法转移到它之后的状态，这时考虑转移它们就没有意义。我们用一些数据结构来维护有意义的状态从而节省时间。 ### 二.斜率优化的使用限制 1. ......

### 斜率优化简介 **问题引入** 给定一个长度为 $n$ 的序列 $a[i]$ ,连续若干个数可以分为一组,将这些数分成若干组,每一组的代价为组内元素和的平方,要求最小化代价 $n\le 2\times 10^5$ **朴素算法** 设 $f[i]$ 表示将前 $i$ 个数分组之后的最小代价, ......

下面用例题来具体阐释斜率优化的思想。 ## 例 1：[P2365](https://www.luogu.com.cn/problem/P2365) 任务安排 题目大意：有 $n$ 个任务要在一台机器上一次完成。 ......

# 斜率优化 ## 大致思想： 将决策点视为若干二维平面上的点，将当前点的已知条件视为斜率，将 $dp_i$ 视为截距。寻找经过某个点且斜率一定的直线的最小截距。（寻找最大截距时需要将 $dp$ 取负，转化为最小，这样维护的凸包就始终是下凸包） ## 凸包的维护： ### 单调队列： 满足条件：满足 ......