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

一类定起终点走格子前缀贡献的最优化DP的贡献转化

模型:

\[dp_{i,j}=\max(dp_{i-1,j}+R(i-1,j),dp_{i,j-1}+U(i,j-1)) \]

目标明确:\((0,0)\to (n,m)\)

两个方向的贡献函数可以转化到一个方向,例如 \(U\to R\)

将贡献函数转化为若干个区间修改的形式(唉没错就是差分)(事实上原本的贡献函数计算一般也是基于前缀和等方式)

转化方式基于:

\((0,0)\to (n,m)\),发生 \(i\to i+1\) 时刻的 \(j\) 坐标若 \(\ge t\),则产生贡献 \(w\)。(没错,要的就是这么拆贡献)。

那么这个贡献等效于发生 \(j:t-1\to t\) 的时刻第一维坐标 \(\le i\)

就可以转化到 \(R\) 上了。

用图像说就是:

http://www.jsqmd.com/news/309706/

相关文章:

  • 英国国民健康服务将试点AI和机器人工具检测诊断肺癌
  • UVA136 丑数 Ugly Numbers
  • 小型语言模型在商业应用中的优势分析
  • 慢一点,并不会让你更安全
  • 使用RAG和FastAPI构建生产就绪的AI智能体
  • 腾讯企业邮箱中山服务商:千万注意这5个合作陷阱!
  • 智能体还是技能?答案是两者并存
  • 佛山腾讯企业邮箱服务商,这些秘密你必须知道!
  • 从数据到动作:一座疆鸿智能MODBUS TCP转PROFIBUS网关的精准制药使命
  • 计算机毕业设计springboot基于springboot的外卖系统 基于 Spring Boot 的在线外卖服务平台设计与实现 Spring Boot 框架下外卖配送系统的开发与应用
  • 计算机毕业设计springboot防疫物资捐赠 基于Spring Boot的防疫物资管理平台设计与实现 Spring Boot框架下的防疫物资捐赠与管理系统开发
  • 英伟达20亿美元注资CoreWeave扩建算力中心,OpenAI招聘放缓引发AI效率思考,千问PC和网页端上线国内最强推理模型
  • 2026年回收厂家权威推荐榜:火锅店打包回收/烘焙设备回收/监控设备回收/茶楼设备回收/配电箱回收/酒店整体设备回收/选择指南
  • 亲测好用!专科生必备8款AI论文工具测评
  • 向量数据库是什么:原理、必要性与应用全景
  • Java毕设选题推荐:基于springboot + vue敬老院管理系统基于springboot的敬老院管理系统【附源码、mysql、文档、调试+代码讲解+全bao等】
  • 基于springboot的教学辅助问答系统 计算机毕业设计选题 计算机毕设项目 前后端分离【源码-文档报告-代码讲解】
  • 向量数据库 vs 向量插件(以 PGVector 为代表):工程边界与选型逻辑
  • VUE3获取子组件实例
  • 主流向量数据库横向对比:选型视角下的全景分析
  • 2026年格力空调供应商厂家最新推荐:软水净水系统/净水系统供应商/分户净水系统/别墅地暖供应商/商务净水系统/选择指南
  • 【通信原理】卫星地面站与卫星车协同工作原理深度解析
  • 【工具变量】城市网络关注度数据(2011-2019)
  • 分页的实现
  • 计算机毕业设计springboot学科竞赛活动报名系统 基于Spring Boot的学科竞赛活动报名与管理系统设计 Spring Boot框架下的学科竞赛活动在线报名平台开发
  • 2026制造业中央空调回收高效服务推荐榜
  • 宏智树AI:终结课程论文“凑字焦虑”,从合格到高分的底层逻辑
  • 2026/1/27
  • 计算机Java毕设实战-基于java+springboot的流浪猫狗救助系统基于springboot的宠物领养救助系统【完整源码+LW+部署说明+演示视频,全bao一条龙等】
  • 线段树区间加维护前缀最值