题解 | #环路运输#

题号 NC51187
名称环路运输
来源 0x55 动态规划-环形与后效性处理

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

在一条环形公路旁均匀地分布着N座仓库，编号为1~N，编号为 i 的仓库与编号为 j 的仓库之间的距离定义为 $dist(i,j)=min⁡(|i-j|,N-|i-j|)$ ，也就是逆时针或顺时针从 i 到 j 中较近的一种。
每座仓库都存有货物，其中编号为 i 的仓库库存量为 $A_i$ 。
在 i 和 j 两座仓库之间运送货物需要的代价为 $A_i+A_j+dist(i,j)$
求在哪两座仓库之间运送货物需要的代价最大

样例

示例1
输入
5
1 8 6 2 5
输出
15

$1 <= N <= 10^6,1 <= A_i <= 10^7$

算法

(单调队列)

环的处理

对于环形问题我们有一个定式:将环断开然后得到一条链，复制一遍接到链尾得到一个长为2N的序列

这样做的一个好处就是，在这样一条长度为 $2N$ 的序列中，任意一个长度为 $N$ 的连续序列都对应到

将环从某一位置断开并展开后得到的序列

试着思考公式转化

如果我们能将公式中的同类项和并，比如将 $A_i和i$ 合并起来，将 $A_j和j$ 合并起来考虑

每次枚举 $i$ 则 $A_i和i$ 都是定值,这时只需要维护一个 $A_j和j$ 的最值就可以求解答案

但是 $dist(i,j)$ 中含有绝对值符号使得我们并不能轻易的将 $i,j$ 分离

但是如果我们按照上述方法得到一个长度为 $2N$ 的序列后我们发现代价的公式可以作如下转化

$A_i+A_j+dist(i,j)$ $\rightarrow$ $A_i+A_j+dist'(i,j)$

其中：

$dist(i,j)=min⁡(|i-j|,N-|i-j|)$ $(1 <= i,j <= N)$

$dist'(i,j)=min⁡(i - j,N-(i-j))$ $(1 <= j <= i <= 2N , i - j <= N - 1)$

我们很容易发现后件的表达式的答案构成的集合和前件表达式的答案构成的集合是相同的

所以我们只需要计算第二个表达式的最大值即可

然而我们发现由于i和j的前面的符号是不确定的所以我们还是无法合并 $A_i和i$ ， $A_j和j$

进一步思考一下公式 $dist'(i,j)=min⁡(i - j,N-(i-j))$ 中的 $min$ 是否是必要的呢？

对于环上的两点，他们顺时针的距离加上逆时针的距离之和必定是环的周长

所以

对于奇数环，较短的那个路径的距离一定是小于环周长的一半
对于偶数环，较短的那个路径的距离一定是小于等于周长的一半

所以公式还可以进一步转化

$A_i+A_j+dist''(i,j)$

其中 $dist''(i,j) = i - j$ $(1 <= j <= i <= 2N , i - j <= N / 2)$

求解答案

我们合并同类项 $A_i+A_j+dist''(i,j)$ = $(A_i + i) + (A_j - j)$

每次枚举 $i$ ,对于 $i$ 而言 $(A_i + i)$ 是定值,所以我们只需要找到一个最大的 $(A_j - j)$ 即可

我们发现 $(i - j <= N / 2)$ , $j$ 永远在一个长度为 $N / 2$ 的区间中，滑动窗口最大值可以用单调队列来优化

用 $res$ 维护全局最大值

枚举 $i$ ，当 $i$ 大于 $N + 1$ 时用单调对列 $O(1)$ 更新答案 $res = max(res,i + A[i] + A[q[hh]] - q[hh])$

最后输出res

时间复杂度 $O(N)$

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 2000010;
int q[N];
LL a[N];
int n;

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%lld",&a[i]);
        a[i + n] = a[i];//破环成链
    }
    LL res = 0;
    int hh = 0,tt = -1;
    for(int i = 1;i <= n * 2;i ++)
    {
        if(hh <= tt && i - q[hh] > n / 2) hh ++;
        if(i >= n + 1) res = max(res,a[i] + a[q[hh]] + i - q[hh]);
        while(hh <= tt && a[q[tt]] - q[tt] <= a[i] - i) tt --;
        q[++ tt] = i;
    }
    printf("%lld\n",res);
    return 0;
}

总结：

环形问题试着破环成链
将公式中的同类项合并