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

相关文章

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http

Java Response返回值的最佳处理方案

《JavaResponse返回值的最佳处理方案》在开发Web应用程序时,我们经常需要通过HTTP请求从服务器获取响应数据,这些数据可以是JSON、XML、甚至是文件,本篇文章将详细解析Java中处理... 目录摘要概述核心问题:关键技术点:源码解析示例 1:使用HttpURLConnection获取Resp

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Java中Switch Case多个条件处理方法举例

《Java中SwitchCase多个条件处理方法举例》Java中switch语句用于根据变量值执行不同代码块,适用于多个条件的处理,:本文主要介绍Java中SwitchCase多个条件处理的相... 目录前言基本语法处理多个条件示例1:合并相同代码的多个case示例2:通过字符串合并多个case进阶用法使用

CentOS7更改默认SSH端口与配置指南

《CentOS7更改默认SSH端口与配置指南》SSH是Linux服务器远程管理的核心工具,其默认监听端口为22,由于端口22众所周知,这也使得服务器容易受到自动化扫描和暴力破解攻击,本文将系统性地介绍... 目录引言为什么要更改 SSH 默认端口?步骤详解:如何更改 Centos 7 的 SSH 默认端口1

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

SpringBoot多数据源配置完整指南

《SpringBoot多数据源配置完整指南》在复杂的企业应用中,经常需要连接多个数据库,SpringBoot提供了灵活的多数据源配置方式,以下是详细的实现方案,需要的朋友可以参考下... 目录一、基础多数据源配置1. 添加依赖2. 配置多个数据源3. 配置数据源Bean二、JPA多数据源配置1. 配置主数据

MySQL索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》:本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1