《算法竞赛进阶指南》0x59 单调队列优化DP

news/2024/4/24 11:00:14/

0x59 单调队列优化DP

在正确性的前提下,及时排除不可能的决策,保持决策集合内部有序和查找决策的高效性。

对于形如 d p i = min ⁡ { d p j + f ( i ) + f ( j ) } dp_i = \min\{dp_j+f(i)+f(j)\} dpi=min{dpj+f(i)+f(j)},都可以尝试使用单调队列优化。

“一个人如果比你小还比你强,那么你就永远不如他”

例如状态转移方程 f i = max ⁡ j ≥ i − r i − l { f j + a i + b j } f_i = \max\limits_{j \ge i-r}\limits^{i-l}\{f_j+a_i+b_j\} fi=jirmaxil{fj+ai+bj}

f i = max ⁡ j ≥ i − r i − l { f j + b j } + a i f_i = \max\limits_{j \ge i-r}\limits^{i-l}\{f_j+b_j\}+a_i fi=jirmaxil{fj+bj}+ai。当前决策集合为 [ i − r , i − l ] [i-r,i-l] [ir,il],当 i i i 增大时,集合的左端点也增大,之前小于 i − r i-r ir 的点之后永远小于 i − r i-r ir,所以可以永远删除。

如果 j < j ′ j<j' j<j f j + b j ≤ f j ′ + b j ′ f_j +b_j \le f_{j'}+b_{j'} fj+bjfj+bj,则 j j j 也可以从决策集合中删除。因为 j j j j ′ j' j 同时在决策集合中时, j ′ j' j 更优秀;且 j j j 一定会更早成为不合法决策点。因此,维护了一个价值的单调队列。

围栏

题意:

n n n 个点, m m m 个人。第 i i i 个人可以选择包含点 s i s_i si,长度不超过 l i l_i li 的一段连续的点,每选择一个可以得到 p i p_i pi 的报酬。

询问如何安排使报酬和最多。

解析:

将所有人按 s i s_i si 升序排序,保证没有后效性。

f i , j f_{i,j} fi,j 表示前 i i i 个人刷到 j j j 的报酬和

对第 i i i 个人:

  • 如果不选或者不选当前点 j j j f i , j = m a x ( f i − 1 , j , f i , j − 1 ) f_{i,j} = max(f_{i-1, j}, f_{i, j-1}) fi,j=max(fi1,j,fi,j1)
  • 选择 j j j ( j ≥ s i 且 j < s i + l i ) (j \ge s_i且j < s_i+l_i) (jsij<si+li) f i , j = max ⁡ k = j − l i s i − 1 { f i − 1 , k + p i × ( j − k ) } f_{i,j} = \max\limits_{k = j-l_i}\limits^{s_i-1}\{f_{i-1, k}+p_i\times (j-k)\} fi,j=k=jlimaxsi1{fi1,k+pi×(jk)}

i i i 不变时,随着 j j j 增大,决策区间的左边界 j − l i j-l_i jli 不断增大,维护 f i − 1 , k − p i × k f_{i-1,k}-p_i \times k fi1,kpi×k 递减的单调队列,从队首转移

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 2e4+10;
const int maxm = 1e2+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int q[maxn], hh = 1, tt;
int f[maxm][maxn]; 
struct person{int s, l, p;bool operator < (const person &b) const{return s < b.s;}
}a[maxm];
int n, m;
int main(){//ios::sync_with_stdio(false);//cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 1; i <= m; i++)cin >> a[i].l >> a[i].p >> a[i].s;sort(a+1, a+1+m);memset(f, 0, sizeof(f));for(int i = 1; i <= m; i++){hh = 1, tt = 0;int p = a[i].p, s = a[i].s, l = a[i].l;for(int k = max(s-l, 0); k < s; k++){int x = f[i-1][k] - p * k;while(hh <= tt && f[i-1][q[tt]]-p*q[tt] <= x)tt--;q[++tt] = k;}for(int j = 1; j <= n; j++){f[i][j] = max(f[i-1][j], f[i][j-1]);if(j >= s && j < s + l){while(hh <= tt && q[hh] < j-l)hh++;if(hh <= tt)f[i][j] = max(f[i][j], f[i-1][q[hh]]-p*q[hh]+ p*j);}}}cout << f[m][n] << endl;return 0;
}


裁剪序列

题意:

长度为 n n n 的序列,分成若干段,每段所有数的和不能超过 m m m,使 每段最大值 的和最小

解析:

f i f_{i} fi 表示前 i i i 个数的最小代价。根据含 i i i 的最后一段长度划分集合 f i = min ⁡ s i − s j ≤ m { f j + max ⁡ j + 1 ≤ k ≤ i a k } f_{i} = \min\limits_{s_i-s_j \le m}\{f_j+\max\limits_{j+1\le k \le i} a_k \} fi=sisjmmin{fj+j+1kimaxak} s i s_i si a a a 的前缀和

如果能在 O ( 1 ) O(1) O(1) 的时间内求出 max ⁡ j + 1 ≤ k ≤ i a k \max\limits_{j+1\le k \le i} a_k j+1kimaxak 的话,时间复杂度为 O ( n 2 ) O(n^2) O(n2)

然后就傻眼了,看了大佬的博客才会的。

在枚举到 i i i 时,假设决策集合的左端点为 j j j时,即将 [ j , i ] [j,i] [j,i] 分成一段且 s i − s j − 1 ≤ m s_i-s_{j-1} \le m sisj1m 的最小的 j j j。此时 f i = f j − 1 + a p 1 f_i = f_{j-1}+a_{p_1} fi=fj1+ap1 a p 1 = max ⁡ j ≤ k ≤ i a k a_{p1} = \max\limits_{j\le k \le i} a_k ap1=jkimaxak

当决策点 u ∈ [ j , p 1 ] u\in[j,p_1] u[j,p1]时, max ⁡ u ≤ k ≤ i a k \max\limits_{u\le k \le i} a_k ukimaxak 值不变, f i = min ⁡ { f u − 1 } + a p 1 f_i = \min\{f_{u-1}\}+a_{p_1} fi=min{fu1}+ap1

f u − 1 f_{u-1} fu1 随着 u u u 减小而减小,所以当 u ∈ [ j , p 1 ] u\in [j,p_1] u[j,p1] 时,最优决策点为 j j j f i = f j − 1 + a p 1 f_i = f_{j-1}+a_{p_1} fi=fj1+ap1

将决策集合 [ j , r ] [j, r] [j,r] 划分为两部分,第一部分为 [ j , p 1 ] [j, p_1] [j,p1],第二部分为 [ p 1 + 1 , i ] [p_1+1, i] [p1+1,i]

在第二部分,设 a p 2 = max ⁡ p 1 + 1 ≤ k ≤ i a k a_{p_2} = \max\limits_{p_1+1\le k \le i} a_k ap2=p1+1kimaxak,当 u ∈ [ p 1 + 1 , p 2 ] u\in [p_1+1, p_2] u[p1+1,p2] 时, max ⁡ u ≤ k ≤ i a k \max\limits_{u\le k \le i} a_k ukimaxak 不变,最优决策点为 p 1 + 1 p_1+1 p1+1 f i = f p 1 + a p 2 f_i = f_{p_1}+a_{p_2} fi=fp1+ap2

以此类推,在按照最大值的位置进行分段。

所以,可以维护单调递减的 a p k a_{p_k} apk。但直接枚举维护的序列时间复杂度还是 O ( n 2 ) O(n^2) O(n2),需要快速求出这些决策点中的最优决策点,即最小值。每次操作都是找到最小值,在头部删除,尾部删除和插入,可以用multiset来维护决策点的对应值 f p k + a p k + 1 f_{p_k}+a_{p_{k+1}} fpk+apk+1

需要注意的是,维护的序列 a p k a_{p_k} apk 中如果有 c n t cnt cnt 个元素,则multiset 中有 c n t − 1 cnt-1 cnt1 个元素。

所以当序列插入后至少有两个元素时,在multiset中插入;删除前序列中至少有两个元素时,在multiset中删除。

每次转移都是 O ( log ⁡ n ) O(\log n) O(logn) 的,所有时间复杂度为 O ( n l o g n ) O(nlog n) O(nlogn)

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e5+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;ll n, m;
ll a[maxn], sum, f[maxn];
int q[maxn], hh = 1, tt = 0;
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; i++)cin >> a[i];for(int i = 1; i <= n; i++)if(a[i] > m){cout << -1 << endl;return 0;}multiset<ll> s;for(int i = 1, j = 1; i <= n; i++){sum += a[i];while(sum > m)sum -= a[j++];//[j,i]while(hh <= tt && q[hh] < j){if(hh < tt)s.erase(s.find(f[q[hh]]+a[q[hh+1]]));hh++;}while(hh <= tt && a[q[tt]] <= a[i]){if(hh < tt)s.erase(s.find(f[q[tt-1]]+a[q[tt]]));tt--;}q[++tt] = i;if(hh < tt)s.insert(f[q[tt-1]]+a[q[tt]]);f[i] = f[j-1] + a[q[hh]];if(!s.empty())	f[i] = min(f[i], *s.begin());}cout << f[n] << endl;return 0;
}

http://www.ppmy.cn/news/47575.html

相关文章

【C++类和对象】类和对象(上){初识面向对象,类的引入,类的定义,类的访问限定符,封装,类的作用域,类的实例化,类对象模型,this指针}

一、面向过程和面向对象初步认识 C语言是面向过程的&#xff0c;关注的是过程&#xff0c;分析出求解问题的步骤&#xff0c;通过函数调用逐步解决问题。 C是基于面向对象的&#xff0c;关注的是对象&#xff0c;将一件事情拆分成不同的对象&#xff0c;靠对象之间的交互完成。…

基于web的小型餐厅餐饮饭馆供货订货系统asp.net+sqlserver

本研究课题重点主要包括了下面几大模块&#xff1a;用户登录&#xff0c;管理员信息管理&#xff0c;类别信息管理&#xff0c;商家信息管理&#xff0c;商品信息管理&#xff0c;订单信息管理&#xff0c;损耗信息管理&#xff0c;退货信息管理&#xff0c;修改密码等功能。。…

【花雕学AI】深度挖掘ChatGPT角色扮演的一个案例—CHARACTER play : 莎士比亚

CHARACTER play : 莎士比亚 : 52岁&#xff0c;男性&#xff0c;剧作家&#xff0c;诗人&#xff0c;喜欢文学&#xff0c;戏剧&#xff0c;爱情 : 1、问他为什么写《罗密欧与朱丽叶》 AI: 你好&#xff0c;我是莎士比亚&#xff0c;一位英国的剧作家和诗人。我很高兴你对我的…

有奖征文|小鱼再进化!OceanBase 4.1免费体验

OceanBase 4.0&#xff08;小鱼&#xff09;的首次亮相是在 2022 年 8 月&#xff0c;作为业内首个单机分布式一体化架构的数据库&#xff0c;4.0 版本兼顾了分布式架构的扩展性和集中式架构的性能优势&#xff0c;在同等硬件条件下实现单机性能赶超集中式数据库的同时&#xf…

Hyperledger Fabric 2.x 环境搭建

一、说明 区块链网络的核心是分布式账本&#xff0c;在这个账本中记录了网络中发生的所有交易信息。 Hyperledger Fabric 是一个是开源的&#xff0c;企业级的&#xff0c;带权限的分布式账本解决方案的平台。Hyperledger Fabric 由模块化架构支撑&#xff0c;并具备极佳的保…

幂等性问题与解决方案

幂等性问题与解决方案 摘要 幂等概念来自数学&#xff0c;表示N次变换和1次变换的结果是相同的。这里讨论在某些场景下&#xff0c;客户端在调用服务没有达到预期结果时&#xff0c;会进行多次调用&#xff0c;为避免多次重复的调用对服务资源产生副作用&#xff0c;服务提供…

机器学习:皮尔逊相关系数——影评相关性分析案例

机器学习&#xff1a;皮尔逊相关系数——影评相关性分析案例 文章目录 机器学习&#xff1a;皮尔逊相关系数——影评相关性分析案例:rocket:1、皮尔逊相关系数概念及公式:rocket:2、案例代码部分 皮尔逊&#xff08;pearson&#xff09;相关系数、 斯皮尔曼&#xff08;spearm…

TypeScript泛型类型和接口

本节课我们来开始了解 TypeScript 中泛型类型的概念和接口使用。 一&#xff0e;泛型类型 1. 前面&#xff0c;我们通过泛型变量的形式来存储调用方的类型从而进行检查&#xff1b; 2. 而泛型也可以作为类型的方式存在&#xff0c;理解这一点&#xff0c;先了解下函数的…

【Vue】Vue-route路由

Vue-router官网 由vue-router模块控制&#xff0c;需要额外安装依赖。参考官网 npm install vue-router --save组成 router-link&#xff1a;路由链接&#xff0c;跳转至路由视图&#xff0c;展示指定路由组件信息router-view&#xff1a;路由视图&#xff0c;展示路由组件信…

SLAM 十四讲(第一版)各章方法总结与理解

SLAM 十四讲&#xff08;第一版&#xff09;各章方法总结与理解 总结十四讲中各章各步骤提到的各种方法&#xff0c;以及具体方法在哪个 c 库中可以调用。目的在于能更直观地了解 slam 过程各步骤到底在做什么&#xff0c;以及是怎么联系在一起的。 2. 初识 SLAM SLAM&#x…

Redis---测试配置及添加slave主机

一、测试集群功能 测试高可用 1、停止 master 主机的 redis 服务 master 宕机后对应的 slave 自动被选举为 master&#xff0c;原 master 启动后&#xff0c;会自动配置为当前 master 的 slave 2、检测集群 mgm68管理主机&#xff0c;查看集群信息 主服务器地址和端口(ID值…

python笔记:datetime

处理日期和时间 1 常量 MINYEAR datetime允许的最小年份 MAXYEAR datetime允许的最大年份 2 数据类型 datetime.date带有属性year,month,daydatetime.time带有属性hour,minute,second,microsecond,tzinfodatetime.datetime带有属性year,month,day,hour,minute,second,…

22勤于思考:gRPC都有哪些优势和不足?

如果你能从专栏的开篇词开始读到这篇文章并且能够在过程中认真思考,那么我相信你目前已经能够对gRPC有了较为充分了解。在专栏的最后几节中,我们抽出一篇文章。来探讨一下gRPC有哪些优势和不足,因为只有这样我们才能取其精华,去其糟粕,学习gRPC框架设计的优点,还能反观出…

Nacos服务端健康检查-篇五

Nacos服务端健康检查-篇五 &#x1f550;Nacos 客户端服务注册源码分析-篇一 &#x1f551;Nacos 客户端服务注册源码分析-篇二 &#x1f552;Nacos 客户端服务注册源码分析-篇三 &#x1f553;Nacos 服务端服务注册源码分析-篇四 上篇分析l服务端的注册服务的整个流程&…

大四的告诫

&#x1f442; LOCK OUT - $atori Zoom/KALONO - 单曲 - 网易云音乐 &#x1f442; 喝了一口星光酒&#xff08;我只想爱爱爱爱你一万年&#xff09; - 木小雅 - 单曲 - 网易云音乐 其实不是很希望这篇文章火&#xff0c;不然就更卷了。。 从大一开始&#xff0c;每天10小时…

mysql 事务的 ACID 特征与使用

事务的四大特征&#xff1a; A 原子性&#xff1a;事务是最小的单位&#xff0c;不可以再分割&#xff1b;C 一致性&#xff1a;要求同一事务中的 SQL 语句&#xff0c;必须保证同时成功或者失败&#xff1b;I 隔离性&#xff1a;事务1 和 事务2 之间是具有隔离性的&#xff1…

【性能测试】5年测试老鸟,总结性能测试基础到指标,进阶性能测试专项......

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 性能测试是为了评…

软文推广:真实有效提升软文排名与收录的三大方法!

软文是一种具有良好传播效果的文体&#xff0c;可以通过在搜索引擎中排名靠前的方式&#xff0c;为品牌或企业带来更多曝光。但是&#xff0c;如何让软文在搜索引擎中得到更好的收录和排名呢&#xff1f;在本文中&#xff0c;我们将讨论如何提升软文的收录和排名&#xff0c;以…

Unity记录3.4-地图-柏林噪声生成 1D 地图及过渡地图

文章首发及后续更新&#xff1a;https://mwhls.top/4489.html&#xff0c;无图/无目录/格式错误/更多相关请至首发页查看。 新的更新内容请到mwhls.top查看。 欢迎提出任何疑问及批评&#xff0c;非常感谢&#xff01; 汇总&#xff1a;Unity 记录 摘要&#xff1a;柏林噪声生成…

深入理解栈:从CPU和函数的视角看栈的管理、从栈切换的角度理解进程和协程

我们知道栈被操作系统安排在进程的高地址处&#xff0c;它是向下增长的。但这只是对栈相关知识的“浅尝辄止”。栈是每一个程序员都很熟悉的话题&#xff0c;但你敢说你真的完全了解它吗&#xff1f;我相信&#xff0c;你在工作中肯定遇到过栈溢出&#xff08;StackOverflow&am…