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

P5785[SDOI2012]任务安排快进到DP式子：\[f(i)=\min\{f(j)+T(i)\times(C(i)-C(j))+m\times(C(n)-C(j))\}\]把\(\min\)去掉，然后拆括号：\[f(i)=f(j)+T(i)\timesC(i)-T(i)\timesC(j)+m\timesC(n)-m\timesC(j)\]移项：\[\underline{f(j

T1Statement你需要将\(n(n\le10^6)\)个数的序列\(x\)划分成若干连续段，设其中一段的所有数之和为\(X\)，那么这段的得分为\(Y=aX^2+bX+c\)，其中\(a,b,c\)已知，求划分得到的最大总得分。\(-5\lea\le-1,|b|,|c|\le10^7,1\lex_i\le100\)。Solution设\(f_i\)表示前\(i\)

二维凸包模板题（luogu.P2742）凸包定义给定二维平面上的点集\(P\)，定义能包含这些点的最小凸多边形为\(P\)的凸包。形象地说，凸包就是一根橡皮筋拉伸，使其包括了点集\(P\)中所有点，然后使橡皮筋收紧，橡皮筋就是\(P\)的凸包。例如，下面用红色线段表示了一个点集的凸包（原创图）：凸

首先我们能够发现，最终得到的答案\(b\)一定为下凸的。但是直接求凸壳肯定不行。具体地，答案的凸壳要满足对于每个\(x\)，\(b_x\)都是整数，即每段斜率都是整数。可以发现找到能包住点集，最贴合的一个这样的\(b\)数组就是答案，因为题目给定的操作让我们每次都只能扩展最贴紧的点。那

施工中，但是目前暂停施工。前言刷cdq分治的时候做到了这题，发现自己不是很懂这个东西，跑回去看自己几个月前写的斜率优化dp笔记，当时认为自己弄得很明白了，但现在看来简直就是皮毛，遂弄明白后写下此文，希望自己之后有更多启发时能继续充实这篇文章。若有不妥之处望指出。如果单调

[AGC044E]RandomPawn题解题目链接AtCoder原题链接Step1.拆环原问题是在环上的问题，考虑将环拆开变成链来处理。因此，我们需要找到一个点，使得操作越过这个点一定不优。令使\(a\)的值最大的位置的下标为\(maxp\)。容易发现，如果现在正处在\(maxp\)上，那么继续操作一定不可

题意大概就是给你\(n\)个点\((0,a_0),(1,a_1),\cdots,(n-1,a_{n-1})\)，用一根直线\(l\)覆盖这些点，要求所有点都在这条直线\(l\)之下，设\(y_0,y_1\)分别为\(l\)与\(x=0,x=n-1\)的交点纵坐标值，求\(\miny_0+y_1\)。显然题目不可能这么弱智，题目还要

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

SDUOpen2023-H、几何、积分、单调栈维护上凸壳题目：https://codeforces.com/gym/104324/problem/H题意：有\(n\)个信号基站，你在边玩手机边走路，手机会自动连接到最近的基站。单位时间花费的流量是到基站距离的平方，现在从起点沿着直线走到终点，并且走的都是横平竖直的直线，单位时间

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

1ay1D。这是一个跑不过双\(\log\)的单\(\log\)做法。考虑双\(\log\)做法是怎么做的。令\(a_i(1\lei\len)\)为给定的\(x\)坐标递增的点序列，开一棵线段树维护区间上凸壳，第\(i\)次查询相当于在\([i+2,n]\)区间组成的点的上凸壳中，找到一个在经过\(a_i,a_{i+1}\)

Luogu1452旋转卡壳，注意判一下平行的情况，另外有个比较简介的求凸包方法，就不用分别求上凸壳和下凸壳再合起来了：intis(pointa,pointb){returna.x==b.x?a.y<b.y:a.x<b.x;}#definepd(A,B,C)(cross((C-B),(B-A))>0||(cross((C-B),(B-A))==0&&is(A,B)==is(B,C)))sort(p+1,p+n+

WQS二分学习笔记目录WQS二分学习笔记用途：思考方式：使用限制：算法思想：用途：WQS二分通常用来解决形如强制选k个且收益最大/代价最小的题目。就比如说：https://www.luogu.com.cn/problem/P5308如果没有限制的话，代码会非常简单思考方式：使用限制：首先要使用WQS二分要有限制：便是最终k

ARC072F设“热量”为\(T_1V_1+T_2V_2+...\)，最后要求的温度就是\(\dfrac{T_1V_1+T_2V_2+...}{V_1+V_2+...}\)，由于最后体积是恒定的，那么我们只需要解决热量的问题即可。设\(f_{i,x}\)表示第\(i\)天晚上只能留下\(x\)升水的最大热量。如果我们把写成函数\(f_i(x)\)，我们

一、凸壳算法凸壳是能包含点集合的最小凸多边形，即凸壳是点集合的一个子集，将这个子集的点连接起来可以包含点集中所有的点。 二、数组中点的凸壳#include<iostream>#include<CGAL/Exact_predicates_inexact_constructions_kernel.h>#include<CGAL/convex_hull_2.h>

概述对于两个点集\(A,B\)来说，把其中的每一个点都看做是对应向量，则这两个集合的闵可夫斯基和定义为\(C=\{a+b|a\inA,b\inB\}\)。凸包的闵可夫斯基和考虑\(C\)为凸包\(A,B\)的闵可夫斯基和，那么\(C\)的大小应该为\(|A||B|\)，但是如果考虑\(C\)的凸包，那么点数应该是

如果一个DP的转移方程可以写成\(f_i=\underset{j<i}{\min\!/\!\max}\>\{f_j+a_i\timesb_j+c_i+d_j\}+C\)的形式，那么可以运用斜率优化。不妨设转移是\(\min\)，设\(g_{i,j}=f_j+a_i\timesb_j+c_i+d_j\)，即\(f_i=\min\limits_{j<i}g_{i,j}\)，式子可以化为\(f_j+d_j=-a_i\time

决策单调性定义：单调矩阵：每行最值位置单调不降。完全单调矩阵：每个子矩阵都是单调矩阵，这里的子矩阵可以不连续。蒙日矩阵：满足四边形不等式的矩阵，蒙日矩阵一定是完全单调

记\(c_i=|i-p_i|\)。可以证明，删掉一个\(c_i\leqs\)的点后，只会让\(c_j>s\)的点的\(c_j\)变小，且原本\(c_j\leqs\)的点的\(c_j\)仍不会大过\(s\)。也就是说我们

感知机​​感知机​​​​三要素分析​​​​模型​​​​策略​​​​损失函数选择​​​​算法​​​​原始形式​​​​对偶形式​​​​相关问题​​​​例子​​​​ir

平面计算几何基础计算几何要解决什么问题？处理点、直线、线段、圆、多边形等几何图形的位置关系。浮点数相关存储方式：符号位F+指数位Z（阶码）+尾数位W\(x=F\timesW\time

凸多边形是指所有内角大小都在\([0,\pi]\)范围内的简单多边形在平面上能包含所有给定点的最小凸多边形叫做凸包。I.jarvis数学构造法现在平面上有这么多个点。