题目描述
环上有 $N$ 个点,每个点有点权 $A_i$,相邻仓库距离为 $1$,任意两点 $i,j$ 之间的距离定义为沿环的两侧分别从 $i$ 前往 $j$ 的距离中的较小值。定义任意两点 $i,j$ 之间的代价为 $A_i+A_j+dis_{i,j}$,求环上最大代价。
解法
注:本题作为蓝书中的例题,代表了一类必须掌握的题型,推荐在参照题解前先尝试自己完成代码。
不难看出使用 $DP$ 求解的基本思路。
本题为环状模型,处理起来有一定难度。处理环状模型有两种常用方法:分类讨论与断环为链。如想要了解分类讨论的思想,可以参照蓝书中的另一道例题 AcWing288 休息时间,本篇题解不展开讨论。下面主要介绍断环为链的思想。
断环为链的思想可以简述为:对于一个长度为 $N$ 的环,我们不妨将其断开并延长一倍,使之变成一条长度为 $2N$ 的链,并将其划分为若干部分分别考虑。
首先把题面中计算代价的算式拆开,可以得到:
$$ f_{i,j}=\left\{ \begin{aligned} &A_i+A_j+i-j\space&(j < i,i-j\leq N/2)\\\ &A_i+A_j+N+j-i\space&(j < i,i-j > N/2)\\\ \end{aligned} \right. $$
在断环为链之后,该算式等价于:在长度为 $2N$ 的链上,$f_{i,j}=A_i+A_j+i-j\space(j < i,i-j \leq N/2)$。
此时,本题已经被转化为了标准的线性 $DP$。
下面我们考虑如何求解该线性模型。如果按照上文推出的算式进行 $DP$,我们需要一维枚举 $i$,一维枚举 $j$,总时间复杂度为 $O(N^2)$。本题中 $N\leq 10^6$,这样的复杂度无法令人满意。考虑优化。
继续观察算式,我们发现该算式可以转化为如下形态:
$$ f_{i,j}=max\{\space (A_j-j)+(A_i+i)\space\}\space(j < i,i-j \leq N/2) $$
其中,当 $i$ 固定时,$(A_i+i)$ 也确定了下来,我们只需要考虑 $(A_j-j)$ 的最大值即可。
考虑对这一部分使用单调队列维护(参见蓝书 0x59
节)。通过这种方式,我们可以在 $O(1)$ 的时间内得到这一部分的最大值。
均摊时间复杂度为 $O(N)$,可以通过本题。
至此,本题得到完美解决。
C++ 代码
#include<cstdio>
#include<iostream>
int a[2000086],q[2000086],h=1,t=0,n;
long long ans;
long long Max(long long a,long long b){return a>b?a:b;}
long long read(){
char ch=getchar();long long nn=0,ssss=1;
while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
return nn*ssss;
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
a[i+n]=a[i];
}
int len=n/2;
q[++t]=1;
for(int i=2;i<=n+len;i++){
while(q[h]<i-len&&h<=t)h++;
ans=Max(ans,(long long)(a[i]+i+a[q[h]]-q[h]));
while(a[q[t]]-q[t]<a[i]-i&&t>=h)t--;
q[++t]=i;
}
printf("%lld",ans);
}
阅(逃
巨佬orz###
## e