四边形不等式优化

四边形不等式优化

应用于类似以下dp转移方程。
f i = min ⁡ 1 ≤ j ≤ i ( w i , j , f i ) f_{i}=\min_{1\le j\le i}(w_{i,j},f_{i}) fi=1jimin(wi,j,fi)
假设 w i , j w_{i,j} wi,j 可以在 O ( 1 ) O(1) O(1) 的时间内进行计算。

在正常情况下,此状态转移方程的时间复杂度是 O ( n 2 ) O(n^2) O(n2)

对于问题 i i i,我们需要考虑所有的有关决策 j j j,但是当其满足决策单调性时,就可以缩小决策空间,减少时间复杂度。

四边形不等式:

约定:

对于类似 a ≤ b ≤ c ≤ d a\le b\le c\le d abcd 都成立,若二元函数 w i , j w_{i,j} wi,j 满足以下条件
w a , c + w b , d ≤ w a , d + w b , c w_{a,c}+w_{b,d}\le w_{a,d}+w_{b,c} wa,c+wb,dwa,d+wb,c
则称 w i , j w_{i,j} wi,j 满足四边形不等式

特别的,若等号永远成立,则称 w i , j w_{i,j} wi,j四边形恒等式

重点:因为四边形不等式是用来优化时间复杂度的,所以四边形不等式给出了一个决策单调性的充分不必要条件

利用决策单调性,可以使用二分查找,使其查询时间复杂度降低为 O ( N log ⁡ N ) O(N \log N) O(NlogN)

区间包含单调性

w b , c ≤ w a , d w_{b,c}\le w_{a,d} wb,cwa,d,则称 w w w​ 满足区间包含单调性

  • 既包含,又满足决策单调性。

  • 满足四边形不等式的形象化图片。

方程:
$$
w_{l,r+1}-w_{l,r}=a_{r+1}-a_{\lfloor\frac{l+r+1}{2}\rfloor}
\
w_{l+1,r+1}-w_{l+1,r}=a_{r+1}-a_{\lfloor\frac{l+r+2}{2}\rfloor}
\

$$

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/356738.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ctfshow 2023 愚人杯 web

easy_signin 观察url&#xff0c;发现base64 &#xff0c;进行解码&#xff0c;原来可以访问文件路径&#xff0c;那我们访问一下index.php ?imgaW5kZXgucGhw查看源代码发现还是base64 解码得到flag 被遗忘的反序列化 <?php# 当前目录中有一个txt文件哦 error_reporti…

华为数通题库HCIP-821——最新最全(带答案解析)

单选11、某台路由器运行IS—IS,其输出信息如图所示&#xff0c;下列说法错误的是? A、邻居路由器的System-ID为0002.0200.2002 B、本路由器是DIS C、本路由器的区域号为49.0001 D、本路由器System-ID为0100.0000.1001 解析&#xff1a;根据输出信…

java获取指定目录,所有类及其注释名称

场景&#xff1a;获取所有类及名称 &#xff08;整理或填写表格需要&#xff09; 效果&#xff1a; 代码&#xff1a; public static void main(final String[] args) {final File currentDirectory new File("D:\\workspace\\petro-bcenter\\src\\main\\java\\com&quo…

【Android WebView】WebView基础

一、简介 WebView是一个基于webkit引擎、展现web页面的控件。Android的Webview在低版本和高版本采用了不同的webkit版本内核&#xff0c;4.4后直接使用了Chrome。 二、重要类 以WebView类为基础&#xff0c;WebSettings、WebViewClient、WebChromeClient为辅助共同完成安卓段加…

经典游戏案例:植物大战僵尸

学习目标&#xff1a;植物大战僵尸核心玩法实现 游戏画面 项目结构目录 部分核心代码 using System; using System.Collections; using System.Collections.Generic; using UnityEngine; using UnityEngine.SceneManagement; using Random UnityEngine.Random;public enum Z…

可解释机器学习之SHAP方法

以Breast cancer wisconsin (diagnostic) dataset数据集为例。 # Built-in libraries import math import numpy as np import pandas as pd# Visualization libraries import matplotlib.pyplot as plt import seaborn as sns# Sklearn libraries # from skle…

vivado、vitis2022安装及其注意事项(省时、省空间)

1、下载 AMD官网-资源与支持-vivado ML开发者工具&#xff0c;或者vitis平台&#xff0c; 下载的时候有个官网推荐web安装&#xff0c;亲测这个耗时非常久&#xff0c;不建议使用&#xff0c;还是直接下载89G的安装包快。 注意&#xff1a;安装vitis平台会默认安装vivado&…

基于大型语言模型的全双工语音对话方案

摘要解读 我们提出了一种能够以全双工方式运行的生成性对话系统&#xff0c;实现了无缝互动。该系统基于一个精心调整的大型语言模型&#xff08;LLM&#xff09;&#xff0c;使其能够感知模块、运动功能模块以及一个具有两种状态&#xff08;称为神经有限状态机&#xff0c;n…

SpringMVC系列六: 视图和视图解析器

视图和视图解析器 &#x1f49e;基本介绍&#x1f49e; 自定义视图为什么需要自定义视图自定义试图实例-代码实现自定义视图工作流程小结Debug源码默认视图解析器执行流程多个视图解析器执行流程 &#x1f49e;目标方法直接指定转发或重定向使用实例指定请求转发流程-Debug源码…

考前刷题练手感(北航期末往年数据结构编程题)

本次因为是考前一天极速刷题&#xff0c;所以没有讲解&#xff0c;若有问题可私信。 目录 一、 查找同时空人员二、 老鼠回家-无回路三、函数调⽤关系四、东二食堂模拟五、栈帧 一、 查找同时空人员 【问题描述】 假设一共有6个手机基站&#xff0c;都具有记录手机连接基站状…

51单片机定时器中断配置

测试环境 单片机型号&#xff1a;STC8G1K08-38I-TSSOP20&#xff0c;其他型号请自行测试&#xff1b; IDE&#xff1a;Keil C51&#xff1b; 定时器配置及主要代码 以定时器T0为例&#xff0c;查看手册&#xff0c;有4种工作模式&#xff1a;模式0&#xff08;16位自动重装载…

软件测试笔记

一、介绍 软件测试是为了尽可能多地发现软件系统中的错误而不是证明软件的正确性。 1、软件缺陷是什么&#xff1f; 软件在使用过程中存在的任何问题都叫软件的缺陷&#xff0c;简称bug。 缺陷的判定标准 软件未实现需求说明书中明确要求的功能——少功能 软件出现了需求说…

Django从入门到精通:First [Django版本.Python面向对象.Web基础.创建Django项目]

文章目录 Django初学者指南1 Django简介1.1 Django的历史1.2 使用Django的知名网站1.4 Django的主要特点1.5 Django的工作原理 2 Django 版本选择2.1 Django 支持的 Python 版本2.2 Django 版本 3 Django 开发 Web 程序3.1 Python知识点3.1.1 Python 函数3.1.2 Python 面向对象…

LabVIEW电机故障监测系统

电机作为工业生产中的关键设备&#xff0c;其故障会导致生产停滞和经济损失。因此&#xff0c;开发一个能实时监控电机状态并预测潜在故障的系统具有重要意义。通过高效的数据采集和分析技术&#xff0c;提升故障诊断的准确性和及时性。 系统组成 该系统由以下部分组成&#…

java:JWT的简单例子

【pom.xml】 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId><version>2.3.12.RELEASE</version> </dependency> <dependency><groupId>org.springf…

Map集合之HashMap细说

最近在看面试题&#xff0c;看到了hashmap相关的知识&#xff0c;面试中问的也挺多的&#xff0c;然后我这里记录下来&#xff0c;供大家学习。 Hashmap为什么线程不安全 jdk 1.7中&#xff0c;在扩容的时候因为使用头插法导致链表需要倒转&#xff0c;从而可能出现循环链表问…

JAVA大型医院绩效考核系统源码:​医院绩效考核实施的难点痛点

JAVA大型医院绩效考核系统源码&#xff1a;​医院绩效考核实施的难点痛点 绩效考核数字化综合管理系统是一个基于数字化技术的管理平台&#xff0c;用于帮助企业、机构等组织进行绩效考评的各个环节的管理和处理。它将绩效考评的各个环节集成到一个系统中&#xff0c;包括目标…

常见的宽基指数基金

指数基金投资指南 ❝ 这篇博客里面的内容主要来自于银行螺丝钉的《定投十年&#xff0c;财务自由》和《指数基金投资指南》这两本书中章“常见的宽基指数”&#xff0c;最近第三次读这本书&#xff0c;打算做一点笔记加深自己的印象。 博客中很多内容是从书中摘抄的&#xff0c…

【数据结构】顺序表实操——通讯录项目

Hi~&#xff01;这里是奋斗的小羊&#xff0c;很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~~ &#x1f4a5;&#x1f4a5;个人主页&#xff1a;奋斗的小羊 &#x1f4a5;&#x1f4a5;所属专栏&#xff1a;C语言 &#x1f680;本系列文章为个人学习…

深入了解 AndroidX ConstraintLayout 中的 Barrier

androidx.constraintlayout.widget.Barrier&#xff08;简称Barrier&#xff09;是 ConstraintLayout 2.0 中引入的一个新特性&#xff0c;它可以极大地简化复杂布局的实现。本文将详细介绍Barrier 的概念、使用方法以及在实际开发中的应用场景。 什么是 Barrier&#xff1f; …