首页 > 其他分享 >决策单调优化动态规划

决策单调优化动态规划

时间:2024-11-02 17:01:51浏览次数:4  
标签:pre sr 决策 sm sl 优化 单调

四边形不等式

决策单调

即对于dp方程\(f[i]=min/max(f[j]+w(j+1,i))\),设\(f[i]\)从\(pre[i]\)转移,有$\forall\ i>j,pre[i] \le pre[j] $

写出\(pre[]\)就是大概这种效果:

111111224444444446666

可以观察到决策单增,那么对于有序表,可以想到利用二分或分治等\(O(logn)\)的算法来优化转移,从而达到\(O(nlogn)\)的时间复杂度

一个重要的证明决策单调的方法就是四边形不等式

(当然,考场上可以感性分析或打个表)

二分+栈

由于决策单调,故相同决策点都是相连的,可以通过二分+栈来维护这些区间

我们反向考虑:分析一个点\(i\)最多能更新到那些点,顺序枚举\(i\)

那么就在二分找第一个从\(i\)转移能够最优的点,往后的区间都是以\(i\)转移为优

当然,如果区间\(i\)完全覆盖了前面的某个区间\(j\)(在\(j\)左端点仍是决策\(i\)更优),就从栈中弹出\(j\)

注意:这种方法要求转移要高效,即w(j,i)要支持预处理或本身较快

分治

挺新的思路

由于决策单调,\(pre[i]\)随\(i\)单调而单调,用类二分的思路

设\(Solve(l,r,sl,sr,k)\)为划分第k段,当前处理\(f[l]\)~\(f[r]\),它们可能从\(f[sl]\)~\(f[sr]\)转移

取区间\(mid\),如果\(f[mid]\)从\(f[sm]\)转移,那么\(f[l]\)~\(f[mid]\)就是从\(f[sl]\)~\(f[sm]\)转移,\(f[mid]\)~\(f[r]\)就是从\(f[sm]\)~\(f[sr]\)转移

出现子问题,支持分治

分治的一个优势在于:贡献区间连续(从\([sl,sr]\)到\([sl,sm]\),\([sm,sr]\)),这意味着即使贡献难以预处理,也可以通过莫队优化,使得贡献计算时间正确

标签:pre,sr,决策,sm,sl,优化,单调
From: https://www.cnblogs.com/zhone-lb/p/18522181

相关文章

  • 数据库中对性能优化的学习
    MySQL性能优化目录MySQL性能优化索引优化SQL语句优化参数优化定期备份表(冷热数据)索引优化选择合适的索引列选择具有高度唯一性的列作为索引列,如用户ID、邮箱等。选择经常被查询的列作为索引列,如订单号、用户ID等。合理使用复合索引在需要同时查询多个条件的情况下,......
  • 当oledig.dll缺少时,有效解决策略
    当系统提示缺少oledlg.dll(注意:原文中的“oledig.dll”可能是“oledlg.dll”的误写,因为“oledlg.dll”是一个常见的DLL文件,而“oledig.dll”则不是)时,这通常意味着某些程序或游戏可能无法正常运行。以下是一些有效解决策略:一、手动下载并替换确定系统位数:首先,需要确定你的......
  • 小龙虾优化算法:原理、与遗传算法区别及应用案例
     一、小龙虾优化算法原理 (一)自然界中的小龙虾行为模拟 小龙虾优化算法(CrayfishOptimizationAlgorithm,COA)是受小龙虾在自然环境中的生存行为启发而提出的。在自然界中,小龙虾有以下几种主要行为: 1. 觅食行为:小龙虾会在其感知范围内搜索食物资源。它们朝着食物浓度......
  • 模型 DOCA(量化决策)
    系列文章分享 模型,了解更多......
  • 推理优化(1)
    吐槽在连续挖了好几个坑之后,又开了一个新的坑:推理优化。它属于一个llm底层的应用,目的是在操作系统层面来优化llm的执行速度进而优化整个模型。那闲话少说,我们正式开始。llm的过程prefill阶段与decoding阶段prefilldecoding这两者的区别是prefill会先把所有的数据进行拿出......
  • LOD优化之Impostors
    Unity下两个Imposters替代体方案的插件介绍——AmplifyImposters与RuntimeImposters(youtube.com)第21章真正的骗子|英伟达开发商---Chapter21.TrueImpostors|NVIDIADeveloperOctahedralImpostors(shaderbits.com)  ......
  • video 标签 缓存优化策略
    在Web开发中,处理视频内容的缓存是一个常见的需求,尤其是在视频播放过程中管理缓存(buffer)以优化用户体验。HTML5的<video>元素及其相关的JavaScriptAPI提供了一些方法来管理和监控视频的缓存状态。HTMLMediaElement缓存(Buffer)<video>元素是HTMLMediaElement接口的一个实......
  • 【EI复现】风-水电联合优化运行分析(Matlab代码实现)
    ......
  • 【顶级EI复现】【最新EI复现】基于共享储能服务的智能楼宇双层优化配置(Matlab代码实现
          ......