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)

，不如暴力。

比如这样的数据：

CPP

仅凭感性分析，我们得知它的最优策略是 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$ 的转移： $$\begin{aligned} 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$。 ## 代码 ```cpp #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 */ ```

文章操作

题解来历

前置知识

分析

相关推荐

评论

P1220 关路灯题解