题解 P3515 【[POI2011]Lightning Conductor】
FlashHu
2018-08-16 16:42:25
疯狂%%%几个月前就秒了此题的Tyher巨佬
借着这题总结一下决策单调性优化DP吧。蒟蒻觉得用数形结合的思想能够轻松地理解它。
首先,题目要我们求所有的$p_i$,那么把式子变一下
$$p_i\ge a_j-a_i+\sqrt{|i-j|}$$
$$p_i=\max\limits_{j=1}^n\{a_j+\sqrt{|i-j|}\}-a_i$$
绝对值看着很不爽,我们把它拆开
$$p_i=\max(\max_{j=1}^i\{a_j+\sqrt{i-j}\},\max_{j=i}^n\{a_j+\sqrt{j-i}\})-a_i$$
单独看前一部分
$$p_i=\max_{j=1}^i\{a_j+\sqrt{i-j}\}-a_i$$
很明显是个要用决策单调性优化的式子。把序列翻转以后,后一部分的算法和前面是一样的,所以只讨论前一部分了。
对于每个$j$,把$a_j+\sqrt{i-j}$看成关于$i$的函数$f_j$。我们要做的就是在所有$j\leq i$的函数中找到最值。比如样例:
![](https://cdn.luogu.com.cn/upload/pic/28914.png)
观察发现,真正有用的函数只有最上面那个!然而实际情况比这个稍复杂些。sqrt的增速是递减的,因此可能存在一个$j$比较小的函数,在某一时刻被$j$比较大的函数反超。我们大概需要维护这样的若干个函数:
![](https://cdn.luogu.com.cn/upload/pic/28913.png)
我们用队列实现决策二分栈(不懂的可以参考一下[蒟蒻的blog](https://www.cnblogs.com/flashhu/p/9480669.html)),按$j$从小到大依次维护这些函数。显然,对于其中任意两个相邻的函数$f_t,f_{t+1}$,它们都有一个临界值$k_{t,t+1}$。显然序列中的$k_{1,2},k_{2,3}...$也要严格递增。否则,如果$k_{t,t+1}\ge k_{t+1,t+2}$,可以想象$f_{t+1}$根本没有用。
先`for`一遍$i$,我们尝试着把$f_i$加入队列。这时候为了保证$k$递增,设队尾决策为$t$,我们判断,如果$k_{t-1,t}\ge k_{t,i}$(此时会有$f_t(k_{t-1,t})\le f_i(k_{t-1,t})$),那么$t$没用,出队。
该出去的都出去后,$i$就可以加入队尾了。这时候可以来求$p_i$了。我们检查一下队首决策$h$,如果$t_{h,h+1}\le i$,说明$h$的巅峰时刻已经过去,出队。最后队首就是所有函数中的最大值。
貌似并没有用到什么三元组啊qwq
update:感谢孤独·粲泽的指正,二分上下界确实该调调
不过还是没有用到什么三元组啊qwq,蒟蒻之前都把临界值$k$存下了,直接用就可以啦
```cpp
#include<bits/stdc++.h>
#define RG register
#define R RG int
#define G if(++ip==iend)fread(ip=buf,1,N,stdin)
#define calc(i,j) a[j]+sq[i-j]//计算函数值
using namespace std;
const int N=5e5+9;
char buf[N],*iend=buf+N,*ip=iend-1;
int n,a[N],q[N],k[N];
double p[N],sq[N];
inline int in(){
G;while(*ip<'-')G;
R x=*ip&15;G;
while(*ip>'-'){x*=10;x+=*ip&15;G;}
return x;
}
inline void chkmx(RG double&x,RG double y){
if(x<y)x=y;
}
inline int bound(R x,R y){//二分临界值k
R l=y,r=k[x]?k[x]:n,m,ret=r+1;//控制二分上下界
while(l<=r){
m=(l+r)>>1;
if(calc(m,x)<=calc(m,y))
ret=m,r=m-1;
else l=m+1;
}
return ret;
}
void work(){
for(R h=1,t=0,i=1;i<=n;++i){
while(h<t&&calc(k[t-1],q[t])<calc(k[t-1],i))--t;//维护k单调
k[t]=bound(q[t],i);q[++t]=i;
while(h<t&&k[h]<=i)++h;//将已经不优的决策出队
chkmx(p[i],calc(i,q[h]));//因为做两遍所以取max
}
}
int main(){
n=in();
R i,j;
for(i=1;i<=n;++i)
a[i]=in(),sq[i]=sqrt(i);
work();
for(i=1,j=n;i<j;++i,--j)//序列翻转
swap(a[i],a[j]),swap(p[i],p[j]);
memset(k,0,(n+1)<<2);
work();
for(R i=n;i;--i)//翻转过了所以要倒着输出
printf("%d\n",max((int)ceil(p[i])-a[i],0));
return 0;
}
```