AcWing 289. 环路运输【环形DP + 单调队列优化】

痛定思痛。 2024-04-19 11:13 50阅读 0赞

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

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

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

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

输入格式

第一行包含一个整数N。

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

输出格式

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

数据范围

1≤N≤10^6  
1≤Ai≤10^7

思路：将数组复制一遍放到数组尾部，对于任意两个点i，j，如果dist(i, j) <= n / 2, 那么dist(i, j) = i - j  ，否则的话dist(i, j) = n - (i - j)

所以原问题就转换成了长度为2n的数组，让你找到两个点i，j，满足i-j <= n / 2， 并且ai + aj + dist(i, j) 最大。

我们考虑用单调队列优化，头部维护满足区间的左端点，尾部判断能否加入更优的点，枚举i，维护最优解。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define ls rt << 1
    #define rs rt << 1|1
    #define mid ((l + r) >> 1)
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    const int maxn = 2e6 + 10;
    const int mod = 1e9 + 7;
    int a[maxn], p[maxn];
    
    int main()
    {
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &a[i]);
            a[i + n] = a[i];
        }
        int head =1, tail = 1, ans = 0;
        p[1] = 1;
        for(int i = 2; i <= 2 * n; ++i)
        {
            while(head <= tail && p[head] + n / 2 <= i)
                ++head; //删除位置不符合的
            ans = max(ans, a[i] + a[p[head]] + i - p[head]);
            while(head <= tail && a[i] - i >= a[p[tail]] - p[tail])
                --tail; //更新加入更优的
            p[++tail] = i;
        }
        printf("%d\n", ans);
        return 0;
    }