不等式
四边形不等式
写的有点答辩了。 [四边形不等式优化](https://oi-wiki.org/dp/opt/quadrangle/) 最简单的一种： 2D1D的状态转移方程： $$f_{l,r}=\min_{k=l}^{r-1}\{f_{l,k}+f_{k+1,r}\}+w(l,r)$$ 当 $w(l,r)$ 满 ......
四边形不等式小整理
原文：[四边形不等式优化dp](https://www.cnblogs.com/a1b3c7d9/p/10984353.html "四边形不等式优化dp") 以下为内容摘录： 若二元函数满足当 $a \leq b \leq c \leq d$，有 $w(a,d)+w(b,c) \geq w(a,c) ......
满足不等式的最大值
你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。 也就是说 points[i] = [xi, yi] ，并且在 1 >& points, int k) { deque q; int n = points.size(); int ......
量子力学的实验验证：双缝实验和贝尔不等式
通过双缝实验和贝尔不等式实验，我们验证了量子力学中的重要概念，并深化了对量子世界的理解。这些实验的结果为我们理解和应用量子力学提供了重要的实验支持，并推动了量子技术的发展。 ......
从决策单调性到四边形不等式
# 从决策单调性到四边形不等式 今天上课浅学了一下，还是有点懵，于是就准备用这篇博文整理一下。 本篇文章主要讨论四边形不等式在有关 1D/1D 类问题中的应用，区间类暂不涉及。 参考：OI-Wiki ## 引入 我们为什么需要决策单调性？ 我们之前常见的 dp 优化有很多，如单调队列，如斜率优化，如 ......
变分不等式笔记
如果对于一个线性空间，其中每一个元素都根据一定法则对应一个实数，满足非负、数乘、三角不等式，则称该线性空间为赋范线性空间，对应的实数称为范数。一言以蔽之，赋范线性空间就是对其中元素定义了范数的线性空间。 用该范数定义赋范空间X的元素的距离 d，该赋范空间就成了距离空间，记作（X, d），因为该范数满 ......
APIO2021《决策单调性与四边形不等式》讲稿与相关材料
两年多过去了，今天还有人加我来问 APIO21 我的四边形不等式讲稿，我一感到受宠若惊，另外对没有及时公开相关材料感到很抱歉。目前所有材料已上传到 [github](https://github.com/Itst00/APIO2021-monge/tree/main)。 ......
随感 - 感受凸性、决策单调性、次模性、四边性不等式之间千丝万缕的联系
凸凸凸凸凸凸凸凸凸凸凸凸凸凸凸凸凸凸凸凸凸凸凸凸凸凸凸。
这些都是凸的！！！！！！凸性太美妙了！！！！！！ ......
非线性规划——不等式约束的最优化方法KT条件（五）
库恩塔克条件(Kuhn-Tucker conditions)是非线性规划领域里最重要的理论成果之一，是确定某点为极值点的必要条件。如果所讨论的规划是凸规划，那么库恩-塔克条件也是充分条件。本文不对数学公式进行详细推导，而是从直观上对KKT条件进行理解。 =w(i,j)+\min_d(c(i,d)+c(d+1,j))$，存在 $w(i,j)+w(i',j')\le w(i,j')+w(i',j)(i\le i'\le j\le j'$ 如何快速求其答案。 引理一：$w(i,j)+w(i',j')\le w(i,j')+w( ......
由切线放缩导出常见函数不等式
$$\def\dif{\mathop{}\!\mathrm{d}}$$ 首先，我们知道泰勒公式 $$f(x)=\sum_{k=0}^n\frac{f^{(n)}(x_{0})}{k!}(x-x_0)^k + R_n(x)$$ 将 $f(x)=e^x$ 在 $x=0$ 处展开可以得到 $$e^x=1+ ......
《决策单调性与四边形不等式》学习笔记（未完结）
参考 psj 的 apio 讲课，《决策单调性与四边形不等式》 p_b_p_b 的学习笔记。 csy 的讲课 oiwiki 一维的决策单调性 将 dp 抽象一下，给定一个向量 $f$ 和一个矩阵 $A$，考虑求出一个向量 $g_i=\min_j(f_j+a_{i,j})$。 如果一个矩阵 $A$ 的 ......
解不等式到底想考啥
前言 高中阶段的许多学生本以为 解不等式 是个比较轻松的工作，结果弄得晕头转向，不知所以，现在试着分层次将其作以梳理。 典例剖析 :writing_hand: 层次一：以考查常用的数学变形和数学运算为主，这类题目主要集中在初中数学层面，高中学生常常会在集合、线性规划等章节中遇到，大多在高一高二的时间 ......
马尔可夫不等式, 切比雪夫不等式, 大数定律
防盗 https://www.cnblogs.com/setdong/p/17325420.html 1. Markov's inequality Theorem: $X$ 为非负随机变量, 且 $\mathbb{E}[X]<\infty$. 那么对于任意 $t>0$ 有 $$ \mathbb{P} ......
四边形不等式学习笔记
简要题意 四边形不等式是一种 dp 优化策略。多用于 2D DP。 内容 对于区间 $[l,r]$ 带来的贡献 $w(l,r)$，如果其满足： 对于 $L\leq l\leq r \leq R$，$w(L,r)+w(l,R)\leq w(L,R)+w(l,r)$ 则称 $w$ 满足四边形不等式。特别 ......
华为OD机试 不等式
本期题目：不等式 题目 给定一组不等式，判断是否成立并输出不等式的最大差（输出浮点数的整数部分） 要求： 不等式系数为 double 类型，是一个二维数组 不等式的变量为 int 类型，是一维数组 不等式的目标值为 double 类型，是一维数组 不等式约束为字符串数组，只能是大于，大于等于，小于， ......
四边形不等式
四边形不等式 基本概述 四边形不等式本质是在决策时利用单调性进行的一种优化，通常与动态规划结合 例题 石子合并 我们先看一道非常经典的问题： 在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出1个 ......
四边形不等式
# 四边形不等式 #### 基本概述 四边形不等式本质是在决策时利用单调性进行的一种优化，通常与动态规划结合 #### 例题 石子合并 我们先看一道非常经典的问题： 在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次 ......
四边形不等式（未修正）
四边形不等式 基本概述 四边形不等式本质是在决策时利用单调性进行的一种优化，通常与动态规划结合 例题 石子合并 我们先看一道非常经典的问题： 在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出1个 ......