参考：https://blog.csdn.net/clove_unique/article/details/57405845
死活不过样例看了题解才发现要用double....
[a_j leq a_i+p-sqrt{abs(i-j)}
]
[pgeq a_j+sqrt{abs(i-j)}-a_i
]
[p = max{a_j+sqrt{abs(i-j)}}-a_i
]
[f_i+a_i = max{a_j+sqrt{abs(i-j)}}
]
首先正反做两遍，这样就不用考虑绝对值了，答案直接从正反连个数组取max即可
然后看这个转移，发现i-j是递增的，也就是j的取值是单调向右移动的
用分治来做dp
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=500005;
int n;
double a[N],s[N],f[N],g[N];
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
void wk(double f[],int l,int r,int x,int y)
{//cerr<<l<<" "<<r<<" "<<x<<" "<<y<<endl;
if(x>y||l>r)
return;
int mid=(l+r)>>1,w;
double p;
for(int i=x;i<=y&&i<=mid;i++)
if((p=a[i]+s[mid-i])>f[mid])
{
w=i;
f[mid]=p;
}
f[mid]-=a[mid];
wk(f,l,mid-1,x,w);
wk(f,mid+1,r,w,y);
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
a[i]=read(),s[i]=sqrt((double)i);
wk(f,1,n,1,n);
for(int i=1;i<=n/2;i++)
swap(a[i],a[n-i+1]);
wk(g,1,n,1,n);
for(int i=1;i<=n;i++)
printf("%.0lf
",ceil(max(f[i],g[n-i+1])));
return 0;
}