Luogu P3515 [POI2011]Lightning Conductor 题解
Luogu P3515 [POI2011]Lightning Conductor 题解
yzxoi
发布于 2022-09-19 11:34:51
发布于 2022-09-19 11:34:51
文章被收录于专栏：OI
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>ji<ji>j1\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
#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("%lld\n",max(f[0][i],f[1][n-i+1]));
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-08-13
，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
