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

【高级算法】单调队列优化动态规划

前言

单调队列优化动态规划就是字面意思——即由单调队列来优化动态规划的一种方法。

前置知识:

  • 动态规划

  • 单调队列

例题

P1725 琪露诺

题目简述

给定一长度为 $N+1$ 的数列 $A$ , 第 $1$ 项为 $0$。

以第一项为起点 , 对于当前的位置 $i$
可以转移到: $(i+L,i+R)$ 中任意一位置
并且获得当前位置上数的价值。

则求出当位置 $≥N+1$ 时可以取得的最大价值和。

思路

一道经典的单调队列优化动态规划问题,对于动态规划,首先要定义状态。

我们定义 $dp[i]$ 表示以 $i$ 结尾能获得的最大值,这个应该很好列出来。

然后我们来推状态转移方程。其实这个也很好推,只不过优化的话要动一点脑子。首先我们可以得到:

$$dp[i] = max(dp[j]) + a[i] (i-R \le j \le i-L)$$

解释一下:就是前面能跳到这个格子的格子里面取一个最大值再加上这个格子本身的价值。

但是!我们发现如果暴力地去枚举 $j$ 会超时,那怎么办呢?

注意到每次求最大值的区间的长度是一个固定的长度,在一个固定长度的区间内求最大值,所以我们联想到单调队列

对于求 $max(dp[j])$ 可以使用单调递减队列求解:

	for(int i=L;i<=n;i++){ll res=i-L;while(head<=tail && dp[res]>=dp[q[tail]]) tail--;q[++tail]=res;while(head<=tail && q[head]+R<i) head++;dp[i]=dp[q[head]]+rock[i];if(i+R>n) ans=max(ans,dp[i]);}

然后我们设最后的队头为 $head$,队列为 $q$,那么状态转移方程就变为:

$$dp[i] = dp[q[head]] + a[i]$$

现在就不超时了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
ll rock[N],dp[N],q[N];//dp[i]表示以结尾的最大值
ll n,L,R,head,tail,ans=-1e9;void init(){memset(dp,128,sizeof dp);dp[0]=0;return ;
}
int main(){cin>>n>>L>>R;for(int i=0;i<=n;i++) cin>>rock[i];init();for(int i=L;i<=n;i++){ll res=i-L;while(head<=tail && dp[res]>=dp[q[tail]]) tail--;q[++tail]=res;while(head<=tail && q[head]+R<i) head++;dp[i]=dp[q[head]]+rock[i];if(i+R>n) ans=max(ans,dp[i]);}cout<<ans;return 0;
}

P2034 选择数字

题目简述

给定一行 $n$ 个非负整数 $a_1 ,\cdots, a_n$。现在你可以选择其中若干个数,但不能有超过 $k$ 个连续的数字被选择。你的任务是使得选出的数字的和最大。

对于 $20%$ 的数据,$n \le 10$。

对于另外 $20%$ 的数据,$k=1$。

对于 $60%$ 的数据,$n \le 10^3$。

对于 $100%$ 的数据,$1 \le n \le 10^5$,$1 \le k \le n$,$0 \le $ 数字大小 $ \le 10^9$。

时间限制 $500$ms。

思路

这道题的思路不太好想,个人觉得特别是状态转移。

首先我们定义 $dp[i][0/1]$ 表示第 $i$ 个数选或者不选,这个挺简单。

然后我们来看状态转移。首先如果不选的话就从上一个数选或者不选里面选一个最大值:

$$dp[i][0] = \max(dp[i-1][0],dp[i-1][1])$$

对于选择这个数,由于 $k$ 的存在,我们不能选择连续 $k$ 个数字,所以如果当前的数字选了,那么前面最多选 $k-1$ 个数字。

所以 $i$ 必须由某一个 $j(j \in [i-k,i-1])$ 转化过来,并且 $j$ 不能被选。

我们记录前缀和数组 $sum$,那么转移方程就是:

$$dp[i][1] = max(dp[j][0] + sum[i] - sum[j])(j \in [i-k,i-1])$$

又注意到 $sum[i] - sum[j]$ 可以拆分:

$$dp[i][1] = \max(dp[j][0]-sum[j])+sum[i](j \in [i-k,i-1])$$

这个就是代码的转移方程了,好了我们终于写完了!
记得最后要在选和不选之中取最大值。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
ll dp[N][2];//dp[i]表示第i项选或者不选的最大值
ll num[N],sum[N],q[N];
ll n,k,head,tail;
int main(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>num[i];sum[i]=sum[i-1]+num[i];}for(int i=1;i<=n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]);//更新dp[i][0]while(head<=tail && dp[i][0]-sum[i]>dp[q[tail]][0]-sum[q[tail]]) tail--;q[++tail]=i;while(head<=tail && q[head]+k<i) head++;dp[i][1]=dp[q[head]][0]-sum[q[head]]+sum[i];//更新dp[i][1]}cout<<max(dp[n][0],dp[n][1]);//最终判断return 0;
}
http://www.hskmm.com/?act=detail&tid=26066

相关文章:

  • MySQL CentOS7 本地安装
  • TypeScript装饰器 - Ref
  • 【笔记】排列与组合学习笔记
  • 【高级数据结构】线段树
  • 【高级数据结构】ST 表
  • 【高级算法】树形DP
  • 【高级数据结构】浅谈最短路
  • C++_基础
  • 2025电位仪厂家最新企业品牌推荐排行榜,纳米粒度及 Zeta 电位仪,Zeta 电位仪公司推荐
  • PCIe扫盲——物理层逻辑部分基础(二)
  • 前沿仿真未来趋势
  • StarRocks与Apache Iceberg:构建高效湖仓一体的实时分析平台 - 详解
  • 斑马打印机打印头更换教程
  • 构造中国剩余定理方程组的解
  • 2025粒度仪厂家最新品牌推荐榜,喷雾粒度分析仪, 激光粒度仪,激光粒度分析仪,纳米粒度仪公司推荐
  • MTK oppoR9m Smart Phone flash Tool 提示 ERROR: STATUS_ABORT(0xC0010002)
  • 二分图最大匹配 Dinic/EK算法
  • 基本Dos指令
  • 2025 年酒店一次性用品源头厂家最新推荐排行榜:含牙签牙线筷子套杯盖杯垫杯套外卖筷子印刷房卡套信封用品优质供应商盘点
  • 2025餐饮一次性用品厂家最新推荐排行榜:聚焦资质口碑与产品实力,助力餐饮企业精准选品!
  • 2025工伤诉讼律师事务所推荐:北京市信之源律所专业维权值得
  • 2025小程序开发公司最新推荐榜,优选杭州网博科技,兼顾用户体验与传播效果
  • 2025企业合同律师事务所推荐:北京信之源律所,专业靠谱之选
  • MTK oppoR9m Smart Phone flash Tool 提示 ERROR: STATUS_PRELOADER_INVALID(0xC0030004)
  • Docker 部署 PostgreSQL 数据库教程
  • 2025年软件外包平台解析:10个不同定位的真实情况
  • P3574 题解 | 贪心,树形 dp
  • 爱,在行动中生长,我们因爱而变得辽阔——《岛上书店》读后感
  • Ubuntu 下同名文件替换后编译链接到旧内容的现象分析 - 实践
  • Luogu P14007 「florr IO Round 1」查询游戏 题解 [ 蓝 ] [ 交互 ]