首页 > 其他分享 >四边形不等式优化

四边形不等式优化

时间:2024-09-13 22:13:10浏览次数:7  
标签:le 不等式 队列 决策 四边形 最优 优化

四边形不等式优化

四边形不等式

对于定义域为整数的二元函数 \(w(i,j)\),如果对于 \(a\le b\le c\le d\),满足 \(w(a,c)+w(b,d)\le w(a,d)+w(b,c)\)(即交叉小于等于包含),则称 \(w(i,j)\) 满足四边形不等式。

还是上面的函数,如果对于 \(a+1<b\),满足 \(w(a,b)+w(a+1,b+1)\le w(a,b+1)+w(a+1,b)\) 则 \(w\) 也满足四边形不等式,可感性理解。

我们用下面这条式子可以更方便的证明某个函数是否满足四边形不等式,当然很多时候我们可以通过打表得出。

决策单调性

最优决策点:我们对于 \(i\),有一个最优的位置 \(j\) 使得 \(f(i)\) 最优,\(j\) 就叫做 \(i\) 的最优决策点,记作 \(opt(i)\),也可能是多个。

决策单调性:对于 \(i<j\),有 \(opt(i)\le opt(j)\)。

我们看下面几条 DP 式:

\[f(i)=\min_{0\le j< i} w(j+1,i) \]

\[f(i)=\min_{0\le j<i}f(j)+w(j+1,i) \]

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

其中,一式是不依赖于之前的 \(f\) 的 DP。

二式是依赖于之前的 \(f\) 的 DP,其可看做一个区间分割问题,\(w\) 是一个区间的代价,同时不限分割个数。

三式是限制分割个数的区间分割问题。

我们可以经过证明得到,当 \(w(i,j)\) 满足四边形不等式时,上述 DP 式一定满足决策单调性(注意 DP 式中一定是 \(\min\))。

\(w(i,j)\) 满足四边形不等式是他们有决策单调性的充分不必要条件。

求解决策单调性

分治法

对于上文中的一式,由于对于每个位置,它不依赖于其他位置的值,所以可以不按顺序地求任意一个位置的最优决策点,于是考虑分治。

设 \(solve(l,r,L,R)\) 表示求 \([l,r]\) 位置的最优决策点,并且已知它们的最优决策点都在 \([L,R]\) 范围内。

于是考虑先求出 \(mid=\lfloor\frac{l+r}{2}\rfloor\) 的最优决策点,我们直接遍历 \([L,R]\) 求它的决策点。

设 \(opt(mid)=d\),于是分治求解 \(solve(l,mid-1,L,d),solve(mid+1,r,d,R)\)。

例题:P3515 [POI2011] Lightning Conductor

对于三式,我们也可以选择用分治,但复杂度可能不优。

具体来说,设最后要分 \(m\) 个区间,则考虑枚举当前这一层选的区间个数,我们一层一层考虑,这样 \(f\) 就不依赖于这一层的 \(f\) 了,而依赖于上一层的 \(f\),此时复杂度为 \(O(mn \log n)\)。

例题:P4767 [IOI2000] 邮局 加强版

二分队列

对于上文中的二式和三式,就不可分治了,于是用二分队列。

对于一个位置 \(i\),它作为 \(j\) 的最优决策点 \(opt(j)=i\) ,满足的 \(j\) 一定形成一个区间 \([l,r]\)。

于是我们从前往后扫到 \(i\),通过我们队列里的最优决策点得到 \(f(i)\),然后求得 \(i\) 对应的区间 \([l,r]\),把三元组 \((i,l,r)\) 压进队列里。

我们队列里的三元组从前往后要满足对于 \(i<j\) 的位置,一定有 \(r_i<l_j\)。

具体来说:

首先初始化队列中只有一个元素 \((0,1,n)\),初始化 \(f(0)\)。

然后从前往后扫,扫到了 \(i\)(设 \(h\) 为头,\(t\) 为尾)。

  1. 一直把满足 \(r_h<i\) 的队头弹掉。

  2. 此时 \(l_h\le i\le r_h\),则此时的 \(i_h\) 就是 \(i\) 的最优决策点,于是计算 \(f(i)\)。

  3. 把可能得 \(r_h\le i\) 的队头弹掉,因为这一部分已经没有用了,方便后续操作。

  4. 一直把满足 \(f(i)+w(i+1,l_t)<f(i_t+1,l_t)\) 的队尾弹掉,注意弹掉前要判断是否 \(l_t\ge i+1\)。

  5. 看队列是否已空。

    5.1. 空,则插入 \((i,i+1,n)\)。

    5.2. 非空,则考虑在 \([\max(i+1,l_t),r_t]\) 二分一个最小的位置 \(j\) 使得 \(f(i)+w(i+1,j)<f(i_t)+w(i_t+1,j)\)。

    若存在这样的 \(j\),说明对于 \([j,r_t]\) 来说,\(i_t\) 没有 \(i\) 优,于是将 \(r_t\) 改为 \(j-1\),同时插入 \((i,j,n)\)。

    若不存在这样的 \(j\),说明 \([l_t,r_t]\) 这段区间内,\(i\) 都没有 \(i_t\) 优,所以判断是否满足 \(r_t<n\),是则插入 \((i,r_t+1,n)\)。

在这里,我们判断是否更优使用了 \(<\),这样可以使决策点尽可能靠前,对于限定区间个数时,这样就会使选的区间个数尽可能少,方便用后续的 wqs 二分优化。而如果我们用 \(\le\),可以使选的区间个数尽可能多。

配合 wqs 二分

如上面的三式,便可以考虑用 wqs 二分去掉要求选择个数 \(m\) 的限制。

此时如上所说,二分队列中符号的选择很重要。

例题:邮局 加强版 加强版

例题:abc355g baseball

标签:le,不等式,队列,决策,四边形,最优,优化
From: https://www.cnblogs.com/dccy/p/18412994

相关文章

  • 多目标优化算法求解36个多目标测试函数(ZDT1、ZDT2、ZDT3、ZDT4、ZDT6、DTLZ1-DTLZ9、W
    36个多目标测试函数(ZDT1、ZDT2、ZDT3、ZDT4、ZDT6、DTLZ1-DTLZ9、WFG1-WFG9、UF1-UF10、LSMOP1-LSMOP3)是专门为了测试和比较不同多目标优化算法的性能而设计的。下面是每个函数集的简要介绍:ZDT(Zitzler-Deb-Thiele)函数集:ZDT系列是一组经典的多目标优化测试函数,由EckartZit......
  • nginx配置文件解释及优化
    Nginx配置文件基本结构Nginx的配置文件主要由几个部分组成:全局块、events块、http块等。全局块:主要设置影响nginx服务器整体运行的配置指令,如工作进程数(worker_processes)、错误日志存放路径(error_log)等。events块:影响nginx服务器与用户的网络连接,如设置网络连接的序列化(multi_accep......
  • 『功能项目』项目优化 - 框架加载资源【41】
    我们打开上一篇40播放动画时禁止点击移动的项目,本章要做的事情是搭建一个资源加载框架,让UI界面,人物模型以及场景都存放在资源文件夹中在运行时加载出来首先在资源商店加载资源将怪物模型放置场景中将普通管线模型切换成URP重命名为Boss01放在资源文件夹里新建Boss01......
  • 面试-性能优化
    让加载更快减少资源体积:压缩代码,资源合并减少访问次数:合并代码(比如webpack打包之后的bundle.js、CSS的雪碧图),SSR(Server-SideRendering)服务器端渲染、缓存使用更快的网络:CDN比如使用Vue的时候不用亲自去下载vue.js到本地,是可以直接用CDN地址来引用的。可以把......
  • 如何实现云资源FinOps优化
    前言在数字化转型的浪潮中,越来越多的企业选择使用云服务来提升业务灵活性和扩展能力。然而,云资源的快速增长同时也带来了成本控制的挑战。FinOps作为一个结合了成本、业务和运维的跨领域实践,旨在帮助企业优化云资源的使用,实现成本透明化、可预测性和控制。云计算的成本挑战云计......
  • demo:tvm优化resnet50 llvm后端cpu上推理
    这是一个完整的例子。使用预训练的resnet50模型,经过tvm优化调整,target=llvm,在cpu上进行推理。最后打印结果是1这个索引代表goldfish importonnxfromtvm.contrib.downloadimportdownload_testdatafromPILimportImageimportnumpyasnpimporttvm.relayasrel......
  • MYSQL进阶-SQL优化篇
    SQL优化-插入数据批量插入:(一次尽量不超过1000条)Insertintotbtestvalues(1,'Tom'),(2,'cat'),(3,Jerny');手动事务提交:starttransaction;insertintotb_testvalues(1,'Tom'"),(2,'Cat'),(3,jerry');insertintotbtestva......
  • 对 Windows Server 2016 进行优化时,可以考虑以下条目:这些步骤可以帮助提高 Windows Se
    对WindowsServer2016进行优化时,可以考虑以下条目:关闭不必要的服务:服务管理:通过“服务”管理工具(services.msc),禁用或设置为手动启动以下服务(根据实际需要):PrintSpooler(如果不使用打印功能)WindowsSearch(如果不需要文件索引)RemoteRegistryBluetoothSupportService(......
  • 广州Altium Designer 软件许可优化实施成功案例
    AltiumDesigner许可证优化助力电子制造企业提效降本实施行业:电子制造与电路设计实施软件:AltiumDesigner软件一、背景概述1.项目背景AltiumDesigner是一款功能强大的电子设计自动化(EDA)工具,广泛应用于电子制造和电路设计领域。某电子制造企业在研发过程中,因电子产品设计日......
  • 如何优化LdapSrvPriority值的设置
    优化LdapSrvPriority值的设置,可以通过修改Windows注册表中的相应条目来实现。具体步骤如下:打开注册表编辑器(regedit)。导航至HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Netlogon\Parameters路径。在右侧窗格中,新建一个DWORD值,命名为LdapSrvPriority。双击该值,输入一个......