首页 > 其他分享 >关于各种优化

关于各种优化

时间:2023-08-01 11:56:27浏览次数:36  
标签:各种 可以 分治 决策 斜率 关于 优化 单调

发现有时候还是会对各种优化比较混乱。

决策单调性

对于 \(i\) 来说,其决策点为 \(j\),那么对于 \(i'\ge i\) ,其决策点 \(j'\ge j\) 。
不存在依赖的可以直接分治,否则需要使用单调栈。

决策点的单调性

对于 \(i\) 来说,对于决策点 \(j\) 和 \(j'\) ,如果存在 \(j\le j'\) ,那么点 \(j\) 一定不劣于 \(j'\) ,反之亦然。
可以使用二分解决。

双指针

同时存在决策单调性与决策点的单调性。
可以直接用两个指针 \(l,r\) 来维护。

函数图像

有时候dp函数或转移函数可能存在某种规律。
如单峰函数,幂函数等,又或者函数存在单调性。

单调栈/单调队列

如果存在 \(i<j\) 使得点 \(j\) 比点 \(i\) 更优,那么点 \(i\) 就一定不会被选择。
如果对于决策点存在某些要求的话,则可以使用单调队列。

cdq分治

如果问题的形式是点 \(i\) 对点 \(j\) 有一个贡献,要求强制在线求每个点的值。
可以使用cdq分治去除强制在线的要求。
当然广义上的分治要更加复杂。

斜率优化

斜率优化有多种情况,不过一般来说是优化 \(dp_i=dp_j+a_i\times b_j+c_i+d_j\) 。也即转移中存在一些项同时与 \(i,j\) 有关。
显然可以先将与 \(i\) 有关的项提出来,与 \(j\) 有关的项全部合并。那么现在剩下的就是 \(a_i\times b_j+c_j\) 。
一般有两种做法,一种是将 \(-a_i\) 视为斜率,那么就相当于有许多点 \((b_j,c_j)\) ,希望找一个点使得截距最大/小。
还可以将 \(b_j\) 视为斜率,那么就相当于有许多线 \(y=b_jx+c_j\),求对于 \(x=a_i\) 的最大的 \(y\) 。
显然对于两种,我们都可以维护上/下凸壳。转移的点事实上以斜率形成了单调栈/队列。
因此,对于查询和修改值一样的,可以直接在单调栈/队列上做。否则可以在凸壳上二分。
对于修改位置不是单调的,就只能维护动态凸壳了。
当然使用李超线段树也是一种选择。

数据结构优化

显然如果存在某些性质则可以用数据结构优化。
需要注意的是分块可以做到优秀的复杂度。

根号分治

将大小小于根号与大于根号的分开讨论。
一般用于给定 \(n\) 个元素,总大小有限制的。

标签:各种,可以,分治,决策,斜率,关于,优化,单调
From: https://www.cnblogs.com/ezlmr/p/17596070.html

相关文章

  • 关于汽车违章抓拍的一些知识点
    电话搞明白了,现在电子抓拍分为2种,一种是固定抓拍可以上12123处理。一种是移动抓拍,这个无法上12123处理。移动抓拍的要到线下处理完以后,12123上就可以查到。然后可以参加学法减分处理。现在12123的学法减分,都是先处理违章交罚款扣分。然后再到12123去学法减分。只不过移动抓拍......
  • 关于API接口应用
    随着互联网技术的发展,API接口已成为众多应用程序开发中的必备工具,它不仅方便了开发者进行应用程序开发,也为应用程序提供了更多的功能和服务。本文将介绍API接口的概念和应用,以及API接口的优势和未来趋势。一、什么是API接口API是ApplicationProgrammingInterface,即应用程序接口。......
  • Java面试题 P28:数据库篇:MySql篇-MySql优化-索引-什么是索引?索引的底层数据结构是什么?
    什么是索引:索引(index)是帮助MySql高效获取数据的数据结构(有序)。在数据之外,数据库还维护着满足特定查找算法的数据结构(B+树),这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法,这种数据结构就是索引。 ......
  • Sychronized 原理,锁升级优化
    Java对象头以32位虚拟机为例普通对象所以以Integer和int为例子Integer8字节对象头+4字节int值,所以大小是int的3倍int4字节int值数组对象如Student[]s=newStudent[8],还包括数组长度length其中markword结构为MarkWord被设计成一个非固定的......
  • Java面试题 P27:数据库篇:MySql篇-MySql优化-Sql语句执行很慢,如何分析呢?
       ......
  • Java面试题 P26:数据库篇:MySql篇-MySql优化-如何定位慢查询?
          ......
  • mysql优化--索引
    mysql优化--索引Mysql索引大概有五种类型:普通索引(INDEX):最基本的索引,没有任何限制唯一索引(UNIQUE):与"普通索引"类似,不同的就是:索引列的值必须唯一,但允许有空值。主键索引(PRIMARY):它是一种特殊的唯一索引,不允许有空值。全文索引(FULLTEXT):可用于MyISAM表,mysql5.6之后也可......
  • 深入理解Java虚拟机(JVM):原理、结构与性能优化
    1.介绍Java虚拟机(JVM)是Java程序的核心执行引擎,负责将Java源代码编译成可执行的字节码,并在运行时负责解释执行字节码或将其编译成本地机器代码。本文将深入探讨JVM的原理、结构以及性能优化的相关技术。2.JVM原理与结构2.1JVM运行时数据区域JVM运行时数据区域由以下几部分组......
  • 关于Python的学习记录(二十_文件的基本操作)
    实际开发中常常会遇到对数据进行持久化的场景,所谓持久化是指将数据从无法长久保存数据的存储介质(通常是内存)转移到可以长久保存数据的存储介质(通常是硬盘)中。实现数据持久化最直接简单的方式就是通过文件系统将数据保存到文件中。计算机的文件系统是一种存储和组织计算机数据的方法......
  • 关于自定义程序打包成jar包,并读取配置
    前言在实际开发过程中,我们有时候有把你编写的一段程序打成jar包的需求,而一些配置是需要去配置文件里面读取关于这项目的一些配置,本人在网络上查询了众多的资料,总的来说可以归为3类1.从数据库读取配置 老生常谈,在dao层从数据库获取配置信息,然后返回到Service层进行业务逻辑......