首页 > 环路运输
开通博客写题解
头像 jzdx（hjh）
发表于 2021-04-27 20:58:53
题号 NC51187名称 环路运输来源 0x55 动态规划-环形与后效性处理 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld题目描述 在一条环形公路旁均匀地分布着N座仓库，编号为1~N，编号为 i 的仓库 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2021-04-24 21:51:31
题意：有一个n个节点的环，每一个节点有一个权值Ai,求两个节点i,j之间的Ai+Aj+dis(i,j)(i到j的距离)最大为多少？ 思路：单调队列首先将环转换成链，即加一段（n+1）~ (2*n),a[n+i]=a[i] (n>=i>=0)。在环上两点的距离小于等于n/2。设Ai+Aj+ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 louhc
发表于 2019-08-26 11:42:51
思路 将数组复制一倍衔接在最后,那么答案就是用单调队列维护一下的最大值即可.注意及时排除已经不满足的状态.复杂度为,常数也比较优秀. 代码 using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 熠丶
发表于 2021-04-26 15:31:19
时间复杂度： 思路 长度为n的环形首先把它拆成长度为2n的链 我们只要求即可 我们可以枚举i,就是个定值，用有限队列维护的最大值，同时要保证这一条件，不符合弹出即可 代码 // Problem: 环路运输 // Contest: NowCoder // URL: https://ac.nowco 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-04-21 19:55:12
Solution 首先观察题目中的定义可以得知，在不区分前后关系的时候判断很复杂。 我们对于这种环形的办法一般都是断环成链，复制一份。 那么这样处理之后，就可以永远保证按照这种的方式求解不会漏掉情况，并且每次我们每次往前选择的 。接下来就是维护转换方程了。 我们要求解的答案是 定长区间的最值问题，使 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”