四边形不等式学习笔记

简要题意

四边形不等式是一种 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入门之算法学习”的完整攻略。 1. 算法学习概述 算法是计算机科学的核心,是解决问题的有效方法。Python作为一种高级编语言,具简单易学、易读易写等特点,非常适合用于算法学习和实现。本攻略将介绍Python入门之算学习的基本知识实践技巧。 2. 算法学习基础 2.1 算法的定义 算法是一组有限的、清晰、可执行的规则,用于解决特定问题…

    python 2023年5月13日
    00
  • C语言数据结构系列队列篇

    C语言数据结构系列队列篇攻略 简介 队列(Queue)是一种先进先出(First In First Out, FIFO)的线性数据结构,类似于排队买票的过程。本篇攻略将带您从以下三个方面深入浅出地了解C语言数据结构系列队列篇: 队列的特点; 队列的实现; 队列的应用。 队列的特点 队列有两个特殊的端点,队头(front)和队尾(rear)。队头指示队列的头部…

    数据结构 2023年5月17日
    00
  • python排序算法的简单实现方法

    下面是关于“Python排序算法的简单实现方法”的完整攻略。 1. 排序算法简介 排序算法是计算机科学中的一种基本算法,它将一组数据按照特定的顺序进行排列。排序算法可以分为内部排序和外部排序两种。内部排序是指所有数据都可以放在内存中进行排序,而外部排序则是指数据量太大,无法全部放在内存中进行排序,需要借助外部存储器进行排序。 常见的内部排序算法有冒泡排序、选…

    python 2023年5月13日
    00
  • python编程通过蒙特卡洛法计算定积分详解

    以下是关于“Python编程通过蒙特卡洛法计算定积分详解”的完整攻略: 简介 蒙特卡洛法是一种常见的数值计算方法,可以用于计算定积分。本教程将介绍如何使用Python编程通过蒙特卡洛法计算定积分,并讨论如何使用该方法进行数值积分。 步骤 1.导入库和定义函数 首先,我们需要导入必要的库,包括numpy和matplotlib。在Python中,可以使用以下代码…

    python 2023年5月14日
    00
  • Java 数据结构与算法系列精讲之哈希算法实现

    Java 数据结构与算法系列精讲之哈希算法实现 什么是哈希算法? 哈希算法是一种能将任意长度的消息压缩到某一固定长度的消息摘要的算法。 通过哈希算法,我们可以将一个任意的大数据量压缩成一段固定长度的数据,这个数据的长度通常比较小,相对于原数据的大小来说,要小得多。哈希算法的压缩特性使得它经常用来进行信息摘要、数据校验、唯一识别等功能,可以很大程度上提高数据的…

    数据结构 2023年5月17日
    00
  • java数据结构排序算法之树形选择排序详解

    Java数据结构排序算法之树形选择排序详解 什么是树形选择排序 树形选择排序是对选择排序的一种改进和优化,它是通过利用完全二叉树的性质对选择排序进行了改进而得到的一种高效的排序算法。 树形选择排序通过将待排序的元素构建成一颗完全二叉树,然后从叶子节点向上比较,选择出最小的元素,并交换位置。这样子,每次选择最小元素的时候,减少了元素之间的比较次数,从而提高了排…

    数据结构 2023年5月17日
    00
  • 使用Python实现遗传算法的完整代码

    下面是详细讲解“使用Python实现遗传算法的完整代码”的完整攻略,包括算法原理、Python实现和两个示例。 算法原理 遗传算法是一种基于自然选择和遗传学原理的优化算法,其主要思想是通过模拟自然界的进化过程,来寻找最优解。遗传算法的实现过程如下: 初始化种群,随机生成一组初始解。 计算适应度,根据问题的目标函数,计算每个个体的适应度。 选择操作,根据适应度…

    python 2023年5月14日
    00
  • C语言数据结构中约瑟夫环问题探究

    C语言数据结构中约瑟夫环问题探究 什么是约瑟夫环问题? 约瑟夫环问题(Josephus problem)是一个经典的问题,据说是Flavius Josephus发现并命名的。该问题描述为,编号从1到n的n个人按照顺时针方向围坐成一圈,每人持有一个密码。从第1个人开始,顺时针方向每次完整的数m个人,然后让这m个人出圈并把他们的密码拿走不算。当到达队尾时,又从队…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部