标签：p2 return JSOI2016 int mid 1000001 灯塔 dp
链接：https://www.luogu.com.cn/problem/P5503
题目描述：对于每一个$i$，求出$h_{j}-h_{i}+\lceil\sqrt|i-j|\rceil$的最大值。
题解：令第$i$个数的答案为$dp_{i}$,打表可以发现$h$具有决策单调性。这一类决策单调性可以采用整体二分的方式求得决策点范围，由于决策点可能相同，所以不能先取整。
```
#include
#include
#include
using namespace std;
double dp[1000001],dp2[1000001],f[1000001];
long long h[1000001],n,p[1000001],p2[1000001];
void solve(int l,int r,int L,int R)
{
int mid=(l+r)/2;
for (int i=R;i>=L;--i)
if (i<mid&&h[i]+f[mid-i]>dp[mid])
{
dp[mid]=h[i]+f[mid-i];
p[mid]=i;
}
if (l==r)
return;
solve(l,mid,L,p[mid]);
solve(mid+1,r,p[mid],R);
return;
}
void solve2(int l,int r,int L,int R)
{
int mid=(l+r)/2;
for (int i=R;i>=L;--i)
if (i>mid&&h[i]+f[i-mid]>dp2[mid])
{
dp2[mid]=h[i]+f[i-mid];
p2[mid]=i;
}
if (l==r)
return;
solve2(l,mid,L,p2[mid]);
solve2(mid+1,r,p2[mid],R);
return;
}
int main()
{
cin>>n;
for (int i=1;i<=n;++i)
{
cin>>h[i];
dp[i]=-1e18;
}
for (int i=1;i<=n;++i)
f[i]=sqrt(i);
solve(1,n,1,n);
solve2(1,n,1,n);
for (int i=1;i<=n;++i)
cout<<(int)(ceil(max(max(dp[i],dp2[i])-h[i],(double)(0))))<
标签：p2,
return,
JSOI2016,
int,
mid,
1000001,
灯塔,
dp
From： https://www.cnblogs.com/zhouhuanyi/p/16983506.html