四边形不等式学习笔记

简要题意

四边形不等式是一种 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\) 满足四边形不等式。特别地,如果上式符号取等,则称其满足四边形恒等式

注:上面的不等式可以记成:交叉小于包含

四边形不等式优化基础:对于一个 dp \(f(i,j)\),如果其最优决策点(即第三维枚举的最优位置) \(s(i,j)\) 满足 \({s(i,j-1)\leq s(i,j) \leq s(i+1,j)}\),则可以用此方法将时间复杂度优化到 \(O(\max i \cdot \max j)\)

类型一

对于一类 dp(多见于把一个序列分成 \(k\) 段,最小化或最大化每一段段贡献的的和),其状态转移方程为(\(\min\) 也可以换成 \(\max\)):

\[f(i,j)=\min_{k=1}^{i-1}{(f(k,j-1)+w(k+1,j))}
\]

\(w\) 满足四边形不等式。则:

  • \(f\) 也满足四边形不等式。
  • \(f\) 满足四边形不等式基础。

SPOJ LARMY - Lannister Army

给出一个长为 \(N\) 的序列 \(H\),你需要将其分成 \(K\) 段,使得每一段的逆序对数量之和最小。输出最小值。

\(1 \leq K \leq N \leq 5\times10^3,1 \leq H_i \leq 10^5\)

不能再板的四边形不等式吧。先推出每一个序列的每一个区间的逆序对数量,然后四边形不等式即可。

时间复杂度 \(O(N^2)\)

P4767 [IOI2000]邮局

在数轴上分布着 \(V\) 个村庄。第 \(i\) 个村庄在 \(a_i\)。两个村庄的距离为这两个村庄的位置之差得绝对值。你需要在一些村庄中修建邮局,你需要输出每一个村庄到离其最近的邮局的距离之和的最小值。

\(1 \leq P \leq 300,1 \leq P \leq V \leq 3 \times 10^3,1 \leq a_i \leq 10^4\)

这道题可以看成将村庄排序后分成 \(P\) 段,每段在其中点修建一个邮局。最小化每段到其中点的距离和的和。

可以递推出每段的贡献 \(w(i,j)=w(i-1,j)+a_j-a_{\lfloor (i+j)\div 2\rfloor}\)

然后,然后就没了。

时间复杂度 \(O(V^2)\)

类型二

对于一类区间 dp 问题(多见于石子合并类),其状态转移方程为(\(\min\) 也可以换成 \(\max\)):

\[f(i,j)=\min_{k=i}^{j-1}{(f(i,k)+f(k+1,j)+w(i,j))}
\]

\(w\) 满足四边形不等式。则:

  • \(f\) 也满足四边形不等式。
  • \(f\) 满足四边形不等式基础。

P1775 石子合并(弱化版)

有一个长度为 \(N\) 的序列 \(m\)。你可以合并相邻的两个元素 \(m_i,m_j\),变成 \(m_i+m_j\),并花费 \(m_i+m_j\) 的代价。输出最小代价和。

\(1 \leq N \leq 300,1 \leq m_i \leq 10^3\)

这道题暴力 \(O(N^3)\) 前缀和 + 区间 DP 可以过,但是容易发现 \(w(i,j)=\sum_{k=i}^{j} m_k\) 满足四边形不等式。于是可以使用四边形不等式优化。

时间复杂度 \(O(N^2)\)

原文链接:https://www.cnblogs.com/zheyuanxie/p/quadrangle.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:四边形不等式学习笔记 - Python技术站

(0)
上一篇 2023年4月17日
下一篇 2023年4月17日

相关文章

  • python算法学习之桶排序算法实例(分块排序)

    下面是详细讲解“python算法学习之桶排序算法实例(分块排序)”的完整攻略,包含两个示例说明。 桶排序算法简介 桶算法是一种线性排序算法,它的基本思想是将数据分到有限数量的桶中,然后对每个桶中的数据进行排序,最后将所有桶中的数据依次取出,即可得到有序序列。桶排序算法适用于数据分布均的情况,时间复杂度为O(n)。 Python实现桶排序算法 下面是Pytho…

    python 2023年5月14日
    00
  • C语言数据结构之简易计算器

    C语言数据结构之简易计算器攻略 简介 这是一个基于C语言的简易计算器,可以实现加、减、乘、除四个基本运算。 实现步骤 首先,需要声明四个变量,分别表示运算符、被加数、被减数、被乘数和被除数。 char op; double n1, n2, result; 然后,需要通过scanf()函数获取用户输入的运算符和数字。 printf(“请输入运算符和数字:\n”…

    数据结构 2023年5月17日
    00
  • Python实现KNN邻近算法

    Python实现KNN邻近算法的完整攻略 KNN算法是一种常用的机器学习算法,用于分类和回归问题。本文将详细讲解Python实现KNN算法的整个攻略,包括算法原理实现过和示例。 算法原理 KNN算法的基本思想是通过计算待分类样本与训练集中所有样本距离选取距近的k样本,根据这k个样本的类别进行投票,将待分类样归票数多的类别。在回归中,KNN算法的基本思想是通过…

    python 2023年5月14日
    00
  • 7个流行的Python强化学习算法及代码实现详解

    下面是关于“7个流行的Python强化学习算法及代码实现详解”的完整攻略。 1. 强化学习简介 强化学习是一种机器学习方法,它的目标是让智能体在与环境交互的过程中学习如何做出最优的决策。强化学习的核心是智能体、环境、状态、动作、奖励和策略。智能体通过观察环境的状态,选择最优的动作,并获得相应的奖励。智能体的目标是通过学习最优的策略,使得长期累积的奖励最大化。…

    python 2023年5月13日
    00
  • Python基于回溯法子集树模板实现8皇后问题

    下面是详细讲解“Python基于回溯法子集树模板实现8皇后问题”的完整攻略。 1. 什么是回溯法 回溯法是一种通过断尝试和回溯来寻找解的算法。它通常用于解决组合问题、排列问题、子集问题等。回溯的基本思想是:从问题的某一种状态开始搜索,当搜索到某一状态时,如果这种状态不是问题的解,则回溯到上一个状态续搜索。 2. 子集树模板 子集树是回溯法的一种常用模板,它通…

    python 2023年5月14日
    00
  • mysql的Buffer Pool存储及原理解析

    下面我就来详细讲解一下“mysql的Buffer Pool存储及原理解析”的攻略。 Buffer Pool简介 在MySQL中,Buffer Pool是一个重要的概念,也可以说是MySQL最重要的性能优化建议之一。Buffer Pool是MySQL内存中缓存数据页的数据结构,用于加速数据的读写。 数据页 在MySQL中,数据是以数据页(page)为单位进行读…

    数据结构 2023年5月17日
    00
  • python中Apriori算法实现讲解

    下面是关于“Python中Apriori算法实现讲解”的完整攻略。 1. Apriori算法简介 Apriori算法是一种经典的关联规则挖掘算法,它可以从大规模数据集中挖掘出频繁项集和关联规则。Apriori算法的核心思想是利用频繁项集的性质,通过逐层扫描数据集,生成候选项集,并通过剪枝操作去除不满足最小支持度的项集,最终得到频繁项集和关联规则。 2. Py…

    python 2023年5月13日
    00
  • 跟老齐学Python之啰嗦的除法

    在Python中,除法运算符/的结果可能会出现小数,这是因为Python默认使用浮点数进行除法运算。但是在某些情况下,我们需要使用整数进行除法运算,这时候就需要使用Python中的整除运算符//。 下面是“跟老齐学Python之啰嗦的除法”的完整攻略: 1. Python中的除法运算符 在Python中,除法运算符/的结果可能会出现小数,例如: >&g…

    python 2023年5月14日
    00
合作推广
合作推广
分享本页
返回顶部