[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=4850
[算法]
首先对不等式进行移项 :
hj <= hi + p - sqrt(|i - j|)
p >= hj - hi + sqrt(|i - j|)
显然 , sqrt(|i - j|)最多只有sqrt(n)个不同的值
用ST表求区间最值 ， 然后分块计算即可
时间复杂度： O(Nsqrt(N))
[代码]
#include<bits/stdc++.h>using namespace std;#define MAXN 200010#define MAXLOG 20#define sqr(x) x * xint n;int lg[MAXN] , bit[25];long long h[MAXN];long long value[MAXN][MAXLOG];template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }template <typename T> inline void read(T &x){ ???T f = 1; x = 0; ???char c = getchar(); ???for (; !isdigit(c); c = getchar()) if (c == ‘-‘) f = -f; ???for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - ‘0‘; ???x *= f;}inline long long query(int l,int r){ ???int k = lg[r - l + 1]; ???return max(value[l][k],value[r - bit[k] + 1][k]);}int main(){ ???????read(n); ???for (register int i = 1; i < MAXN; i++) lg[i] = (double)log(i) / log(2.0); ???bit[0] = 1; ???for (register int i = 1; i <= 20; i++) bit[i] = bit[i - 1] << 1; ???for (register int i = 1; i <= n; i++) read(h[i]); ???for (register int i = 1; i <= n; i++) value[i][0] = h[i]; ???for (register int i = 1; i < MAXLOG; i++) ???{ ???????for (register int j = 1; j + (1 << i) <= n; j++) ???????{ ???????????value[j][i] = max(value[j][i - 1],value[j + bit[i - 1]][i - 1]); ???????} ???????} ???????for (register int i = 1; i <= n; i++) ???{ ???????int l = i , r , sq = 1; ???????long long ans = 0; ???????while (l != 1) ???????{ ?????????????????????????????r = l - 1; ???????????l = max(1,i - sqr(sq)); ???????????chkmax(ans,sq + query(l,r) - h[i]); ???????????sq++; ???????} ???????????r = i , sq = 1; ???????while (r != n) ???????{ ???????????l = r + 1; ???????????r = min(n,i + sqr(sq)); ???????????chkmax(ans,sq + query(l,r) - h[i]); ???????????????sq++; ???????????????} ???????printf("%lld\n",ans); ???} ???????return 0;}[JSOI 2016] 灯塔
原文地址：https://www.cnblogs.com/evenbao/p/9745529.html