首页 > 其他分享 >四边形不等式 学习笔记

四边形不等式 学习笔记

时间:2024-09-01 21:25:39浏览次数:8  
标签:le 不等式 决策 笔记 DP QI 四边形 单调

四边形不等式 学习笔记

定义

四边形不等式(QI)如果对于函数 \(w(l, r)\),\(l_1\le l_2\le r_1\le r_2, w(l_1, r_1) +w(l_2, r_2)\le w(l_1, r_2) + w(l_2, r_1)\),则称 \(w\) 满足四边形不等式,函数 \(w\) 的二维矩阵被称作蒙日矩阵。

一般只能用于求 \(\min\) 的DP。

石子合并模型

对于 DP 方程:

\[f_{l, r} = \min_{k\in[l, r - 1]}(f_{l, k} +f_{k + 1, r}) + w(l, r) \]

如果 \(w\) 满足 QI 与 包含单调性(\([l, r]\subseteq[ll, rr], w(l, r)\le w(ll, rr)\)),则 \(f\) 满足 QI,且 \(f\) 具有决策单调性,具体而言,设 \(m(l, r) = \text{arcmin}_{k} (f_{l, k} +f_{k +1, r})\),则有 \(m(l,r-1)\le m(l, r)\le m(l+1, r)\),证明可以反证+放缩法。

利用决策单调性可以把这个 DP 在 \(O(n^2)\) 的时间复杂度内计算出来,具体而言记录每个状态的最优决策点,转移上下界只需要枚举到上不等式即可,这样对于每一层 \(m(l, r - 1)\le m(l,r)\le m(l + 1, r)\le m(l + 1, r + 1)\le m(l+2,r+1)\),所以对于相同长度的状态,他们这一层总共的枚举量是 \(O(n)\) 的。

分 \(k\) 组模型

对于 DP 方程:

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

如果 \(w\) 满足 QI 和包含单调性,则 \(f\) 具有决策单调性,\(m(l,r-1)\le m(l, r)\le m(l+1, r)\)。

运用决策单调性,可以用分治法在 \(O(nk\log n)\) 的时间内解决这个问题。

使用同石子合并的技巧,可以在 \(O(n^2)\) 的时间内解决这个问题。

1D-1D模型

对于 DP 方程:

\[f_{i} = \min_{j <i} f_{j} +w(j, i) \]

如果 \(w\) 满足QI,则对于 \(a\le b, m(b)\ge m(a)\),证明依旧运用 QI + 放缩。

运用决策单调性,使用二分栈在 \(O(n\log n)\) 的时间内解决这个问题,具体而言,对于每个决策点,考虑哪些状态以它为最优决策点,枚举决策点,维护每个状态当前的最优决策点,然后对于新来的决策点,以它为最优决策点的状态一定是一段后缀,二分出后缀开头即可。

存在 \(O(n)\) 的算法,名字是 SMAWK。

标签:le,不等式,决策,笔记,DP,QI,四边形,单调
From: https://www.cnblogs.com/MoyouSayuki/p/18391759

相关文章

  • Datawhale X 李宏毅苹果书 AI夏令营-跟李宏毅学深度学习(入门)Task3笔记
    目录一、机器学习框架&实践攻略1.总览2.训练误差较大时:    1.模型偏差    2. 优化问题3.训练误差较小时:    1.测试误差较小:    2.测试误差较大:            1.过拟合    2.不匹配一、机器学习框架&实......
  • 简单了解数据库--笔记03
    一、分组查询[groupby]count() //统计计数sum()//求和avg()//平均值min()//最小值max()//最大值group_concat()//拼接函数1.查询每个国家人口总数selectcountrycode,sum(population)fromcitygroupbycountrycode;//给国家分组2.查询中国每个......
  • 简单了解数据库--笔记02
    一、数据库的字符集编码设置utf-8utf8mb41.查看数据库默认的字符集MariaDB[(none)]>showvariableslike"%character%";+--------------------------+----------------------------+|Variable_name|Value|+--------------------......
  • Unclutter - 苹果电脑(Mac)桌面文件笔记剪贴板管理工具
    刚收拾好的电脑桌面马上又堆满了杂七杂八的文件?刚随手一记的笔记,回头却找不到了?马上来认识一下Unclutter,一款藏在Mac系统顶部的文件、笔记、剪贴板管理器。安装后,用户只需要将鼠标指针移动到屏幕顶部,向下滚动,Unclutter窗口就会滑落显现,无需给电脑桌面「添乱」。有时候......
  • Redis基础知识学习笔记(二)
    文章目录一.Redis安装1.Windows下安装1>资源管理器目录进入2>目录进入命令:3.配置环境变量2.Linux下安装1>安装redis2>启动redis3>查看redis是否启动二.Redis配置1.查看配置2.编辑配置3.参数说明三.Redis数据类型1.String(字符串)常用命令实例2.Hash(哈希)......
  • Datawhale X 李宏毅苹果书 AI夏令营 深度学习入门笔记02
    目录一、学习资料二、学习笔记(一)线性模型1、考虑周期性2、修改模型(二)模型变形之分段线性曲线1、分段线性直线2、分段线性曲线的图像和表达式(机器学习第一步:写出带有未知数的函数)(1)如何构成(2)如何表达(3)如何改进3、分段线性曲线的损失(机器学习第二步:定义损失)4、分段......
  • Datawhale X 李宏毅苹果书 AI夏令营 深度学习进阶笔记02
    目录一、学习资料二、学习笔记(一)自适应学习率(adaptivelearningrate)1、什么是+为什么要用2、三种自适应学习率方法(1)AdaGrad(AdaptiveGradient)(2)RMSprop(RootMeanSquaredpropagation)(3)Adam(Adaptivemomentestimation)(二)学习率调度(learningratescheduling)1、为什么......
  • 读书笔记(11)《瓦尔登湖》
    序言这是一本由美国作家梭罗独居瓦尔登湖畔的记录,描绘了他两年多时间里的所见、所闻和所思。在这本书中,梭罗通过建造木屋的过程,对农场的向往和购买经历,以及对生活的理解和追求,向我们展示了他的生活态度和价值观。梭罗在书中表达了对阅读的重要性的深刻理解,他认为阅读可以帮助我......
  • 学习笔记 ---- 基环树
    目录算法解析基环树与基环森林模板例题[NOIP2018提高组]旅行[ZJOI2008]骑士[IOI2008]IslandLongWaytobeNon-decreasing算法解析基环树与基环森林基环树是指有且仅有一个环的树。基环森林是指若干棵基环树构成的森林。对于有向图,基环树可分为内向基环树和外向基环......
  • STM32笔记(10)——USART
    USART(UniversalSynchronous/AsynchronousReceiver/Transmitter)通用同步/异步收发器USART是STM32内部集成的硬件外设,可根据数据寄存器的一个字节数据自动生成数据帧时序,从TX引脚发送出去,也可自动接收RX引脚的数据帧时序,拼接为一个字节数据,存放在数据寄存器里自带波特率发生......