Luogu P3515 [POI2011]Lightning Conductor 题解

题意

题目传送门
已知一个长度为$n$的序列$a_1,a_2,…,a_n$。
对于每个$1\leq i\leq n$,找到最小的非负整数$p$满足 对于任意的$j$,$ a_j \leq a_i + p – \sqrt{| i-j | }$

思路

首先先把题目中的式子化简一下:
$p\geq a_j+\sqrt{|i-j|}-a_i$

原来就是求对于每个$1\leq i \leq n$,对于任意的$j$,求出$a_j+\sqrt{|i-j|}-a_i$的最大值啊~~~
考虑跑两次决策单调性,一次$i>j$,另一次$i<j$,那么就可以把绝对值去掉了。
这里就只考虑$i>j$的情况。
对于每个$1\leq i \leq n$,只要求出最大的$a_j+\sqrt{i-j}$即可。
然而发现$a_j+\sqrt{i-j}$可以决策单调性优化。
也就是说,当i增大时
$a[j1]+sqrt(abs(i-j1))$增大值比$a[j2]+sqrt(abs(i-j2))$增大值小。
存在一个临界点$k$
对于$j2+1<=i<=k,a[j1]+sqrt(abs(i-j1))>a[j2]+sqrt(abs(i-j2))$
对于$k<i,a[j1]+sqrt(abs(i-j1))<a[j2]+sqrt(abs(i-j2))$
考虑使用分治来做决策单调性优化。
$Solve(l,r,ql,qr)$表示在区间$[ql,qr]$中,已经决策出最大值在区间$[l,r]$中。
对于每次$Solve(l,r,ql,qr)$直接暴力扫一遍$[l,r]$求出其中的最大值,所以在区间$[ql,mid-1]$中,最大值肯定在$[l,这个区间的最大值所在位置]$,同理,在区间$[mid+1,qr]$中,最大值肯定在$[这个区间的最大值所在位置,r]$。
那么就好了呀O(∩_∩)O。

Code

暂无评论

发送评论


				
上一篇
下一篇