当前位置: 首页 > news >正文

四边形不等式

首先介绍四边形不等式 a <= b <= c <= d 用于解决一个对于单调性的神秘不等式
f(i) = 对于所有函数参数范围内的数op(i)
设代价函数为w(i , j) 那么 w(a , c) + w(b , d) <= w(a , d) + w(b , c)
那么我们的f(i)将满足单调性
具体证明是这样的!
第一个反证法:显然,这两个式子唯一影响不等号变化的是b , c。
我们设一个对于w(a , b)的最优解(最大或最小,等等),当然就叫这个东西为p(x)好了
对于c < d 有条件 a = p(d) < p(c) = b 根据这两个条件,我们有 w(a , d) < = w(b , d)
和w(b , c) < w(a , c) 移一下项,我们可以发现有 w(a , d) - w(b , d) <= 0 < w(a , c) - w(b , c)
链接起来会发现与原四边形不等式的变形 w(a , c) - w(b , c) <= w(a , d) - w(b , d)相反,证毕。
第二个则是通过二阶差分,即差分的差分,可以发现,对于具有单调性的w(i , j),他们的差分必须都 > 0
那就再做一遍差分,让这个差分 >= 0再变化变化式子就可以了。

http://www.hskmm.com/?act=detail&tid=31174

相关文章:

  • 20251014 杂题
  • 二叉树的遍历
  • SQL在智能自动化业务场景中的应用 - Irving11
  • 拼接字符串要求字典序最小
  • 高级语言作业第一次随笔
  • C#实现开机自启动应用多种方式
  • 日志|二叉树|110平衡二叉树|111二叉树的最大深度|199二叉树的右视图
  • Chrome在Speedometer 3.1创下历史最高分,为用户节省数百万小时
  • 西电CTF平台——Moectf 2025 WriteUP
  • [笔记]并查集进阶(带权、扩展域、带删除)
  • 20251013 模拟赛 总结
  • 什么是反应式编程 - 详解
  • SDL3和其附属的编译记录
  • Qwen多模态系列模型笔记—Qwen2-VL
  • WPF 调用 ChangeWindowMessageFilterEx 修改指定窗口 (UIPI) 消息筛选器的用户界面特权隔离
  • 实验1 现代C++基础课程
  • 牙科诊所借力AI营销4个月创收13万
  • 10月14日日记
  • P4653 [CEOI 2017] Sure Bet
  • 20251014
  • PHP虚拟主机测试页面
  • 歌词本。 - Slayer
  • 10月14日
  • 使用 Docker 快速搭建 MinIO 文件存储服务
  • 2025.10.14 正睿二十连测
  • singleton_pattern
  • ai出题
  • Python的Numpy、Pandas和Matplotlib(随笔)
  • 财务怎样做到业财融合 - 智慧园区
  • CF2146E