题解 P3515 【[POI2011]Lightning Conductor】
题解似乎很少啊
感谢zsy的指点 题解参考了其他人的题解
dp的方程多想一下就可以出来
dp[i]=max(num[j]-num[i]+sqrt(abs(i-j)));然后我们考虑怎么优化它
是不是感觉abs有点难搞？
我们先从前往后做一遍dp，令j<i。 再从后往前做一次，令j>i，这样把abs去掉。
对于函数y=sqrt(x)，它增长的速度应当是越来越慢的
我们先考虑从前往后的情况，如果决策点j不变的情况下，如果i不断增大，那么sqrt(i-j)的增长速度是不是不断减小？
注意到我们的dp方程是要取最大值
如果i不断增大的情况下，决策点j产生的dp值增增长幅度不断减小（注意，他仍然在增长），是不是可能存在一个决策点k，虽然他之前产生的贡献比较小，但是增幅较大，在此时决策点k将代替决策点j形成dp[i]的最优解？
可能有点绕口，类比速度和加速度的关系多想一想
那么，对于每一个决策点j，他可能形成最优解的范围应当是一段区间l到r
这样，我们可以得到一个优化dp的思路
我们可以开一个单调队列，队列里每个结点保存的是三元组{p,L,R};
就是在对于决策点p，他所能管辖到的范围是l到r，队列里所有l和r拼起来就是当前的i到n
每次枚举到一个i的时候，我们将队头的l++（满足队列区间之和为i到r），如果队头的元素所管辖的区间为空，是不是就可以删去了？
此时对于dp[i]而言，队头存储的p是不是就是最优决策点？
此时如果对于dp[n]而言，决策点p并没有决策点i优，我们是不是要在队尾加入决策点i？
那么怎么求i的管辖范围呢？
显然，此时的r=n(想一想为什么)，注意到增长速度是存在单调性的，及对于某一时刻，p突然就没有i优了，以后就一直没有i优了，所以我们可以二分临界值
二分的临界值为temp，则原队尾的r更新为temp-1，加入新的元素i，plr依次为i，temp，n
给个代码：
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define il inline
#define rg register
#define ll long long
#define N 540000
#define inf 2147483647
#define ll_inf 9223372036854775807
using namespace std;
int n,num[N];
double F[N],G[N];
struct T{
int p,l,r;
}Q[N];
il void re(rg int &x);
double sol(rg int i,rg int j){
return (double)num[j]+sqrt((double)(1.0*abs(i-j)));
}
int find(rg int le,rg int ri,rg int p,rg int i){
rg int ans=-1;
while(le<=ri){
rg int mid=((le+ri)>>1);
if(sol(mid,p)>sol(mid,i))le=mid+1;
else ri=mid-1,ans=mid;
}
return ans;
}
int main(){
freopen("s.in","r",stdin);
re(n);
for(rg int i=1;i<=n;++i)
re(num[i]);
//dp[i]=max(num[j]-num[i]+sqrt(abs(i-j)));
//需要求出最优的解
rg int tail=0,head=1;
for(rg int i=1;i<=n;++i){
Q[head].l++;
if(head<=tail&&Q[head].r<Q[head].l)head++;
if(head>tail||sol(n,i)>sol(n,Q[tail].p)){
while(head<=tail&&sol(Q[tail].l,Q[tail].p)<sol(Q[tail].l,i))tail--;
if(head>tail)
Q[++tail].p=i,Q[tail].l=i,Q[tail].r=n;
else{
rg int temp=find(Q[tail].l,Q[tail].r,Q[tail].p,i);
Q[tail].r=temp-1;
Q[++tail].p=i,Q[tail].l=temp,Q[tail].r=n;
}
}
F[i]=sol(i,Q[head].p)-num[i];
}
reverse(num+1,num+n+1);
tail=0,head=1;
for(rg int i=1;i<=n;++i){
Q[head].l++;
if(head<=tail&&Q[head].r<Q[head].l)head++;
if(head>tail||sol(n,i)>sol(n,Q[tail].p)){
while(head<=tail&&sol(Q[tail].l,Q[tail].p)<sol(Q[tail].l,i))tail--;
if(head>tail)
Q[++tail].p=i,Q[tail].l=i,Q[tail].r=n;
else{
rg int temp=find(Q[tail].l,Q[tail].r,Q[tail].p,i);
Q[tail].r=temp-1;
Q[++tail].p=i,Q[tail].l=temp,Q[tail].r=n;
}
}
G[i]=sol(i,Q[head].p)-num[i];
}
reverse(G+1,G+n+1);
for(rg int i=1;i<=n;++i)
printf("%d\n",max(0,(int)ceil(max(F[i],G[i]))));
return 0;
}
il void re(rg int &x){
rg int res=0;rg int w=1;char c=getchar();
while((c<'0'||c>'9')&&c!='-')c=getchar();
if(c=='-')w=-1,c=getchar();
while(c>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0',c=getchar();
x=w*res;
}