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

四边形不等式优化DP

目录

  • 四边形不等式内容
    • [HNOI2008]玩具装箱
      • 解析
      • 代码实现
    • 参考资料

四边形不等式内容

TODO

[HNOI2008]玩具装箱

解析

  • 满足四边形不等式,决策具有单调性. 对于两个位置 i , j i, j i,j, 对应的最优决策点一定有 o p t [ i ] < = o p t [ j ] opt[i] <= opt[j] opt[i]<=opt[j]
  • 代码实现
    • 需要有一个队列,这里我们使用c++里的双端队列( d e q u e deque deque). 因为需要在队尾插入和弹出,队首弹出的操作.
    • 初始化时,队列里只有一个元素, 比如本题中区间 [ 1 , n ] [1, n] [1,n], 决策点为 0 0 0. 这个对所有的位置 [ 1 , n ] [1, n] [1,n]都是合法的一个决策
    • 每次插入决策 x x x的时候,从队尾开始判断,如果当前的节点的区间的开始位置决策 x x x更优,就弹出队尾,一直这么做.
    • 接上一步, 于是就找到了一个节点(当前队尾): 对应的区间开始位置 x x x不优,结束位置 x x x更优。所以存在一个临界点,我们二分就是要找这么一个位置 p o s pos pos. [ p o s , n ] [pos, n] [pos,n]这部分 x x x更优,其他位置不变.
    • 主函数循环部分,我们维持队列的区间都是还未确定最优决策的部分。
    • 主函数循环部分,当循环到位置 i i i时候,由于我们已经考虑过小于 i i i的所有决策,因此对于位置 i i i,队首的决策就是位置 i i i的最优决策.

代码实现

#include <bits/stdc++.h>
using namespace std;#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endifconst int N = 5e4 + 5;typedef long long LL;int n, L;
// 原数组,以及前缀和
vector<LL> a, sum;
// dp[i]: 前i个玩具的最小费用. dp[i] = min(dp[j] + (s[i] - s[j] + i - j - 1 - L)^2), 0 <= j < i
vector<LL> dp;
// f[i]的最优决策点是谁, 也就是f[i]取得最小值的时候对应的上面的式子中的j. opt[i] = j.
vector<int> op;struct Node {int l, r, c;Node(int _l, int _r, int _c): l(_l), r(_r), c(_c){}
};// 存在插入队尾,弹出队首,弹出队尾三种操作,因此我们使用deque
deque<Node> q;// dp方程: f[j] = f[i] + (x - L) ^ 2
inline LL val(int j, int i) {LL s = sum[i] - sum[j] + i - j - 1 - L;return dp[j] + 1LL * s * s;
}// 用决策x更新
void insert(int x) {// pos表示能更新的那一段的开始位置, 结束位置一定是nint pos = n + 1; // 临界点// 找到x能更新的队列,一定是末尾的一段// 队列里队尾的元素. 看决策x是否是更优的决策. 满足'<='意味着x更优while (q.size() && val(x, q.back().l) <= val(q.back().c, q.back().l)) {pos = q.back().l; // 更新pos: [q,back().l, q.back().r] 这一段肯定x更优q.pop_back();}// 找到了这个区间. 这个区间的右边界x更优,左边界x不优秀. 我们二分寻找临界点在哪里if (q.size() && val(x, q.back().r) <= val(q.back().c, q.back().r)) {int l = q.back().l, r = q.back().r;while (l < r) {int mid = l + r >> 1;if (val(x, mid) <= val(q.back().c, mid)) r = mid; // 对于mid这个点, x的决策更优, 临界点在左边 -> [l, mid]else l = mid + 1; // mid这个点,x不优. 那么临界点在右半部分 -> [mid + 1, r]}// 结束循环时,r是使x成为最优决策的一段的起始位置pos = r;q.back().r = r - 1;}// 说明存在某些位置x的决策比当前队列的优. 也就是进入过上面的代码.if (pos != n + 1) q.push_back(Node(pos, n, x));
}int main() {cin >> n >> L;a = sum = dp = vector<LL>(n + 1, 0);op = vector<int>(n + 1, 0);for (int i = 1; i <= n; i++) cin >> a[i], sum[i] = sum[i - 1] + a[i];q.push_back(Node(1, n, 0)); // 一开始队列只有一个元素,表示[1, n]所有的最优决策点都是0for (int i = 1; i <= n; i++) {// 队头的决策点就是当前i的最优决策int opt = q.front().c;dp[i] = val(opt, i);op[i] = opt;// 弹出已经无用的决策if (q.front().r == i) q.pop_front();q.front().l = i + 1;// 插入当前决策,并用决策i去更新 [i + 1, n]的最优决策insert(i);}cout << dp[n] << endl;return 0;
}

参考资料

  • OIWIKI
  • 洛谷日报

相关文章:

四边形不等式优化DP

目录 四边形不等式内容[HNOI2008]玩具装箱解析代码实现 参考资料 四边形不等式内容 TODO [HNOI2008]玩具装箱 解析 满足四边形不等式&#xff0c;决策具有单调性. 对于两个位置 i , j i, j i,j, 对应的最优决策点一定有 o p t [ i ] < o p t [ j ] opt[i] < opt[j]…...

Gin 学习笔记01-数据返回

Gin 数据返回 1、返回 string 和 json2、返回 xml 和 ymal3、返回html4、重定向 1、返回 string 和 json c.String()c.JSON() package mainimport ("github.com/gin-gonic/gin""net/http" )func getJSON(c *gin.Context) {//c.String(http.StatusOK, &qu…...

【AI考证笔记】NO.1人工智能的基础概念

目录 一、什么是智能 1.什么是智能 2.智能的种类 二、什么是人工智能 1.人工智能之父——图灵 2.人工智能的定义 三、人工智能的发展阶段 四、哪些工作要被淘汰掉&#xff1f; 以下部分内容来自于百度智能云人才认证培训讲义&#xff0c;腾讯等也有人工智能类似的讲义&…...

【Exception】npm ERR! code UNABLE_TO_GET_ISSUER_CERT_LOCALLY

Talk is cheap, show me the code. 环境 | Environment kversionOSwindows 11nodev18.14.2npm9.5.0 报错日志 | Error log >npm create vitelatest Need to install the following packages:create-vite5.0.0 Ok to proceed? (y) y npm ERR! code UNABLE_TO_GET_ISSUER_…...

持续集成交付CICD:GitLabCI 通过trigger触发流水线

目录 一、理论 1.GitLabCI 二、实验 1.搭建共享库项目 2.GitLabCI 通过trigger触发流水线 三、问题 1.项目app02未触发项目app01 2.GitLab 报502网关错误 一、理论 1.GitLabCI (1) 概念 GitLab CI&#xff08;Continuous Integration&#xff09;是一种持续集成工具…...

Java 多线程中的sleep()和wait()方法的区别

Java 多线程中的sleep()和wait()方法的区别 1、相同点 sleep()和wait()都可以暂停线程的执行。 2、不同点 所在类不同 sleep()是Thread类的静态方法。 wait()是Object类的方法。 锁释放不同 sleep()是不释放锁的。 wait()是释放锁的。 用途不同 sleep()常用于一定时间内暂停…...

车载以太网-数据链路层-VLAN

文章目录 车载以太网VLAN(Vehicle Ethernet VLAN)车载以太网VLAN帧格式VLAN帧报文VLAN帧报文示例车载以太网VLAN(Vehicle Ethernet VLAN) 车载以太网VLAN(Vehicle Ethernet VLAN)是一种在车辆网络中使用的虚拟局域网技术。它允许在车载以太网网络中创建多个逻辑网络,从…...

【Vue】filter的用法

上一篇&#xff1a; vue的指令 https://blog.csdn.net/m0_67930426/article/details/134599378?spm1001.2014.3001.5502 本篇所使用指令 v-for v-on v-html <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"&…...

python web项目导包规范

python web项目导包规范 python 内置的模块通过第三方库安装的模块框架自身提供的模块用户自己定义的模块 如&#xff1a; from __future__ import absolute_import, unicode_literalsfrom debug_toolbar.panels import Panelfrom django.utils.translation import ugettext_…...

AtCoder Beginner Contest 330 题解

目录 A - Counting PassesB - Minimize Abs 1C - Minimize Abs 2D - Counting LsE - Mex and Update A - Counting Passes 原题链接 题目描述 给定N个数和一个整数L&#xff0c;输出大于等于L的数的个数。 public static void solve() throws IOException{int n readInt(), m…...

论文速读《DeepFusion: Lidar-Camera Deep Fusion for Multi-Modal 3D Object Detection》

概括主要内容 文章《DeepFusion: Lidar-Camera Deep Fusion for Multi-Modal 3D Object Detection》提出了两种创新技术&#xff0c;以改善多模态3D检测模型的性能&#xff0c;通过更有效地融合相机和激光雷达传感器数据来提高对象检测的准确性&#xff0c;尤其是在行人检测方面…...

关于前端处理后端轮询的操作 (总结)

使用场景&#xff1a;前端首次发起请求获取数据&#xff0c;若失败则每隔1s发起一次知道成功获取数据为止解决方案&#xff1a; 使用轮询操作&#xff0c;涉及定时器的使用和关闭 &#xff08;使用vue2代码为例) data() {return {pollingResult_en: null, // 处理轮询结果bizI…...

【SpringCloud】设计原则之单一职责与服务拆分

一、设计原则之单一职责 设计原则很重要的一点就是简单&#xff0c;单一职责也就是所谓的专人干专事 一个单元&#xff08;一个类、函数或微服务&#xff09;应该有且只有一个职责 无论如何&#xff0c;一个微服务不应该包含多于一个的职责 职责单一的后果之一就是职责单…...

UDP分片和丢包与TCP效果对比

UDP 分片 与 丢包&#xff0c;UDP 真的比 TCP 高效吗&#xff1f; UDP&#xff08;用户数据报协议&#xff09;和TCP&#xff08;传输控制协议&#xff09;在很多方面都有显著的区别。总体来说&#xff0c;TCP更适合需要可靠传输的应用&#xff0c;例如网页浏览、电子邮件等&a…...

Inport 模块

文章目录 Interpolate datainport 模块存在于模型最顶层Port Dimension 和 Variable-size signal Interpolate data Interpolate data&#xff1a;当将 Workspace 的数据导人模型时, 对没有对应数据点的采样时刻进行线性插值的开关选项。 inport 模块存在于模型最顶层 inpo…...

Deep Learning for Monocular Depth Estimation: A Review.基于深度学习的深度估计

传统的深度估计方法通常是使用双目相机&#xff0c;计算两个2D图像的视差&#xff0c;然后通过立体匹配和三角剖分得到深度图。然而&#xff0c;双目深度估计方法至少需要两个固定的摄像机&#xff0c;当场景的纹理较少或者没有纹理的时候&#xff0c;很难从图像中捕捉足够的特…...

点云从入门到精通技术详解100篇-基于深度学习的稀疏点云障碍物检测(续)

目录 3.1 连续帧点云空间特征融合 3.1.1 点云预处理 3.1.2 地面分割 3.1.3 自适应点云聚类...

使用VSCode+PlatformIO搭建ESP32开发环境

Arduino IDE本来就是为创客们开发的&#xff0c;虽然没代码提示功能&#xff0c;文件的关系也不清晰&#xff0c;函数不能跳转&#xff0c;头文件也打不开&#xff0c;但人家的初衷就是为了简单而生的&#xff1b;但还是有一些同学喜欢高级点的IDE&#xff0c;也没问题&#xf…...

使用flask返回json格式的数据

Flask Flask是一个使用Python编写的轻量级Web框架&#xff0c;它的设计理念是保持简单、灵活和易扩展。它的核心是Werkzeug和Jinja2&#xff0c;并且它本身只提供了非常基础的Web框架功能&#xff0c;例如路由和请求处理等。 使用Flask可以快速创建一个Web应用程序&#xff0c;…...

如何排查java 内存溢出OutOfMemoryError?

当使用Spring Boot进行文件上传时&#xff0c;文件会被读取到内存中进行处理。如果上传的文件较大&#xff0c;会占用大量的内存空间&#xff0c;从而导致内存溢出&#xff08;OutOfMemory&#xff09;问题。以下是一些建议的排查方案&#xff1a; 调整 JVM 内存设置&#xff…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

多元隐函数 偏导公式

我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式&#xff0c;给定一个隐函数关系&#xff1a; F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 &#x1f9e0; 目标&#xff1a; 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z​、 …...

flow_controllers

关键点&#xff1a; 流控制器类型&#xff1a; 同步&#xff08;Sync&#xff09;&#xff1a;发布操作会阻塞&#xff0c;直到数据被确认发送。异步&#xff08;Async&#xff09;&#xff1a;发布操作非阻塞&#xff0c;数据发送由后台线程处理。纯同步&#xff08;PureSync…...