[JSOI2016]灯塔
[JSOI2016]灯塔
https://ac.nowcoder.com/acm/problem/20227
分析
读完题,我们发现为了满足所有节点 。通过不等式变形 。那么我们就有了 的做法,是过不了的,所以必须优化,我们现在为了去掉绝对值符号,所以考虑从左到右和从右到左分别进行一次转移。令 。那么,根据 的函数图像非常容易得到
那么满足这个式子的,我们直接通过决策单调性优化就好了,时间复杂度为 ,在 上还有一个加强版 。卡掉了分块+rmq的做法。
代码
#include<bits/stdc++.h> using namespace std; const int N = 5e5 + 10,inf = 2e9; int ans[2][N],h[N],n; int read() { int x=0;char ch = getchar(); while(!isdigit(ch)) {ch = getchar();} while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}return x; } void solve(int l,int r,int vl,int vr,int opt) { int mid = l + r >> 1; double Max = -2e9;int pos = 0; for(int p = vl;p <= mid && p <= vr;p++) { double val = h[p] - h[mid] + sqrt(mid - p); if(val > Max) { pos = p;Max = val; } } ans[opt][mid] = ceil(Max); if(l <= mid - 1) solve(l,mid-1,vl,pos,opt); if(mid + 1 <= r) solve(mid+1,r,pos,vr,opt); } int main() { n = read(); for(int i = 1;i <= n;i++) h[i] = read(); solve(1,n,1,n,0); reverse(h+1,h+1+n); solve(1,n,1,n,1); reverse(ans[1]+1,ans[1]+1+n); for(int i = 1;i <= n;i++) { printf("%d\n",max(ans[1][i],ans[0][i]) ); } }