Luogu P3515 [POI2011]Lightning Conductor 题解
题意
题目传送门 已知一个长度为n的序列a_1,a_2,…,a_n。 对于每个1leq ileq n，找到最小的非负整数p满足 对于任意的j, a_j leq a_i p - sqrt{ i-j }
思路
首先先把题目中的式子化简一下： pgeq a_j sqrt{i-j}-a_i 原来就是求对于每个1leq i leq n，对于任意的j,求出a_j sqrt{i-j}-a_i的最大值啊~~~ 考虑跑两次决策单调性，一次i>ji<ji>j1leq 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
代码语言：javascript复制#include<bits/stdc .h>
#define LD double
#define int long long
using namespace std;
int n,a[500010],f[2][500010];
LD calc(int x,int y){
return (LD)(sqrt((LD)abs((x-y))) (LD)a[x]);
}
void solve(int l,int r,int ql,int qr,int dd){
if(l>rql>qr) return;
int s=l,mid=ql qr>>1ll;
double tmp=-19260817.19260817;
for(int i=l;i<=r&&i<=mid;i )
if(tmp<=calc(i,mid)) tmp=calc(i,mid),s=i;
f[dd][mid]=max(f[dd][mid],((int)tmp) (((LD)((int)tmp))!=(LD)tmp)-a[mid]);
solve(l,s,ql,mid-1ll,dd);
solve(s,r,mid 1ll,qr,dd);
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i ) scanf("%lld",a i);
solve(1,n,1,n,0);
for(int i=1;i<=n/2;i ) swap(a[i],a[n-i 1]);
solve(1,n,1,n,1);
for(int i=1;i<=n;i ) printf("%lldn",max(f[0][i],f[1][n-i 1]));
}
