AcWing 289. 环路运输,《算法竞赛进阶指南》,单调队列优化dp,滑动窗口求最大值,环形与后效性处理

本文主要是介绍AcWing 289. 环路运输,《算法竞赛进阶指南》,单调队列优化dp,滑动窗口求最大值,环形与后效性处理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

289. 环路运输 - AcWing题库

在一条环形公路旁均匀地分布着 N 座仓库,编号为 1∼N,编号为 i 的仓库与编号为 j 的仓库之间的距离定义为 dist(i,j)=min(|i−j|,N−|i−j|),也就是逆时针或顺时针从 i 到 j 中较近的一种。

每座仓库都存有货物,其中编号为 i 的仓库库存量为 Ai。

在 i 和 j 两座仓库之间运送货物需要的代价为 Ai+Aj+dist(i,j)。

求在哪两座仓库之间运送货物需要的代价最大。

输入格式

第一行包含一个整数 N。

第二行包含 N 个整数 A1∼AN。

输出格式

输出一个整数,表示最大代价。

数据范围

2≤N≤106,
1≤Ai≤107

输入样例:
5
1 8 6 2 5
输出样例:
15

 解析:单调队列,动规

如果使用暴力的方法我们可以使用两个循环,一个枚举i,另一个枚举j

仔细观察这道题,我们可以发现一下性质
 dist(i,j)=min(|i−j|,N−|i−j|)在 | i - j |<n/2 情况下,dist(i,j)=i-j;同时代价 Ai+Aj+dist(i,j) 可以转化成  Ai+i+Aj-j。

所以我们只需要枚举 i ,然后求出 i 右边 len=n/2 的范围内的最大的 Aj-j 即可

到这里可以看出来这可以单调队列来解决

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 2e6 + 5;
int n, m;
int w[N], q[N];int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &w[i]);w[i + n] = w[i];}int hh = 0, tt = -1;int len = n / 2;int ret = 0;for (int i = 1; i <= 2 * n; i++) {if (hh <= tt && i - q[hh] > len)hh++;ret = max(ret, w[i] + w[q[hh]] + i - q[hh]);while (hh <= tt &&w[q[tt]]- q[tt] <= w[i] - i)tt--;//这一步让队列从左往右变得单调,且左边的值最大q[++tt] = i;}printf("%d\n", ret);return 0;
}

这篇关于AcWing 289. 环路运输,《算法竞赛进阶指南》,单调队列优化dp,滑动窗口求最大值,环形与后效性处理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/155638

相关文章

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

Spring Boot结成MyBatis-Plus最全配置指南

《SpringBoot结成MyBatis-Plus最全配置指南》本文主要介绍了SpringBoot结成MyBatis-Plus最全配置指南,包括依赖引入、配置数据源、Mapper扫描、基本CRUD操... 目录前言详细操作一.创建项目并引入相关依赖二.配置数据源信息三.编写相关代码查zsRArly询数据库数

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

JavaScript错误处理避坑指南

《JavaScript错误处理避坑指南》JavaScript错误处理是编程过程中不可避免的部分,它涉及到识别、捕获和响应代码运行时可能出现的问题,本文将详细给大家介绍一下JavaScript错误处理的... 目录一、错误类型:三大“杀手”与应对策略1. 语法错误(SyntaxError)2. 运行时错误(R

Python实现自动化接收与处理手机验证码

《Python实现自动化接收与处理手机验证码》在移动互联网时代,短信验证码已成为身份验证、账号注册等环节的重要安全手段,本文将介绍如何利用Python实现验证码的自动接收,识别与转发,需要的可以参考下... 目录引言一、准备工作1.1 硬件与软件需求1.2 环境配置二、核心功能实现2.1 短信监听与获取2.