P1220 关路灯 题解

· · 题解

题解来历

这题其实是有 \mathcal{O}(n) 做法的。 —— grass8cow

upd on 25.7.25 感谢 KobeBeanBryantCox 的指正，非常抱歉在题解中出现如此严重的错误，以及给题解审核员带来了不必要的麻烦。

前置知识

斜率优化，单调队列。

分析

发现操作序列一定是向左走若干步，调头向右，再向左……的形式。

如果每个点我们都用最快的时间到达，那么答案即为：\sum\limits_{i=1}^n |p_c-p_i|\cdot w_i。

显然，这个条件是无法满足的，每一次向左或向右移动，答案都会增加，因此，我们设 dp_i 表示从 c 移动到 i，再移动回 c 时至少会让答案增加多少。

假设我们有 l\le c\le r，现在要从 l 转移到 r，显然有方程：

dp_r=dp_l+2\cdot(p_r-p_c)\cdot\left(\sum\limits_{i=1}^{l-1}w_i+\sum\limits_{i=r+1}^n w_i\right)

记 s_u=\sum\limits_{i=1}^u w_i 则有：

dp_r=dp_l+2\cdot(p_r-p_c)\cdot(s_{l-1}+s_n-s_r)

拆开之后，显然是一个斜率优化的式子。从 r 到 l 的转移是对称的。

实现的时候，我们可以先令 l=r=c，向两边扩展。每次选择答案较小的一边转移。发现这样做斜率 |p_i-p_c| 具有单调性，因此可以直接单调队列维护，复杂度 \mathcal{O}(n)。

以上做法是原题解，可惜它是错误的。

为什么呢，发现这样子做，对于 l_1<l_2<c，可能会出现 dp_{l_1}<dp_{l_2} 的情况，因此我们不能使用双指针进行转移，而要每次遍历一边找到最小值，如此还要维护整个凸壳，在凸壳上二分，成功劣化成了 \mathcal{O}(n^2\log n)，不如暴力。

比如这样的数据：

5 4
1 1000 
2 1000 
3 2
4 1
5 100

仅凭感性分析，我们得知它的最优策略是 4 3 2 1 5，但是代码却会给出 4 5 3 2 1 的答案。

因此，我们在 dp 时需要同时保证：对于 l_1<l_2<c<r 如果 dp_{l_1},dp_{l_2} 同时由 r 转移得到，有 dp_{l_1}\ge dp_{l_2}，r 是类似的。

怎么办？对于 dp_l，l-1 的贡献不应该由它承受，而应该让 r 承受，记：

f_r&=dp_r-(p_r-p_c)(s_n-s_r)\\ f_l&=dp_l-(p_c-p_l)s_{l-1} \end{aligned}

得到 f 的转移：

f_r&=f_l+2(p_r-p_l)s_{l-1}\\ f_l&=f_r+2(p_r-p_l)(s_n-s_r) \end{aligned}

发现，我们将本该计算在 dp_l 中的 (p_c-p_l)\cdot s_{l-1} 计算在了 f_r 中，从而保证了 f 数组的单调性。

发现 f 的转移十分简单，以及实际意义：当走到 i 时答案增加的最小值。

如果你足够厉害，应该是能直接设出 f 而不会像我一样设出一个相当 naive 的 dp。

代码

#include "iostream"
#include "cstdio"
#include "cmath"
using namespace std;
const int maxn=55+6;
int w[maxn],dis[maxn],dp[maxn];
struct Node { int x,y;};
inline double calc(Node a,Node b) {return 1.0*(a.y-b.y)/(a.x-b.x);}
struct Deque {
    Node q[maxn]; int l,r;
    Deque() {l=1,r=0;}
    inline void ins(int u,int v) {
        // cout<<"ins:"<<u<<" "<<v<<'\n';
        Node t={u,v};
        while(l<r&&calc(q[r-1],q[r])>=calc(q[r-1],t)) --r;
        q[++r]=t;
    }
    inline int ask(int u) {
        while(l<r&&u>calc(q[l],q[l+1])) ++l;
        // cout<<"qry:"<<u<<" "<<q[l].y<<" "<<q[l].x<<'\n';
        return q[l].y-q[l].x*u;
    }
}L[2];
int main() {
    int n,c; cin>>n>>c;
    int ans=0;
    for(int i=1;i<=n;++i) cin>>dis[i]>>w[i];
    for(int i=1;i<=n;++i) {
        ans+=abs(dis[c]-dis[i])*w[i]; 
        w[i]+=w[i-1]; // cout<<ans<<'\n';
    }
    int l=c,r=c;
    L[1].ins(-w[l-1],-2*dis[c]*w[c-1]); L[0].ins(w[c]-w[n],2*dis[c]*(w[n]-w[c]));
    while(1!=l&&r!=n) {
        int qr=L[1].ask(2*dis[r+1]),ql=L[0].ask(-2*dis[l-1]);
        if(ql<qr) dp[--l]=ql,L[1].ins(-w[l-1],dp[l]-2*dis[l]*w[l-1]);
        else dp[++r]=qr,L[0].ins(w[r]-w[n],dp[r]+2*dis[r]*(w[n]-w[r]));
        // cout<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<dp[l]<<" "<<dp[r]<<'\n';
    }
    if(l==1) ans+=dp[1];
    else ans+=dp[n];
    cout<<ans;
    return 0;
}
/*
5 3
2 10
3 20
5 20
6 30
8 10
*/