标签：决策单调性DP，单调队列，二分
题目
Description
已知一个长度为n的序列a1,a2,…,an。 对于每个1<=i<=n，找到最小的非负整数p满足 对于任意的j, aj < = ai + p - sqrt(abs(i-j)) Input
第一行n，(1<=n<=500000) 下面每行一个整数，其中第i行是ai。(0<=ai<=1000000000)
Output
n行，第i行表示对于i，得到的p
Sample Input 6
5
3
2
4
2
4
Sample Output 2
3
5
3
5
4
分析
先普通DP,f[i]就是对应的P
\[f[i]=max\{a[j]+sqrt(abs(i-j))\}-a[i]\]显然，这样做法时间复杂度是O(n^2)，因为这题是1D1D（就是存在n种状态，每种状态存在n种转移）
把绝对值去掉
\(f[i]=max\{a[j]+sqrt(i-j)\}-a[i]\ (i>=j)\) \(f[i]=max\{a[j]+sqrt(j-i)\}-a[i]\ (i<j)\)
这两个式子很显然决策单调，然后可以用单调队列优化+二分
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=5e5+6;
int n,a[maxn];
double f[maxn],g[maxn];
struct node{int l,r,p;}que[maxn];
double cal(int j,int i){return a[j]+sqrt(abs(i-j))-a[i];}
int find(node t,int x){
int l=t.l,r=t.r,mid;
while(l<=r){
mid=(l+r)>>1;
if(cal(t.p,mid)>cal(x,mid))l=mid+1;else r=mid-1;
}
return l;
}
void dp(double *F){
int head=1,tail=0;
rep(i,1,n){
que[head].l++;
if(head<=tail&&que[head].r<que[head].l)head++;
if(head>tail||cal(i,n)>cal(que[tail].p,n)){
while(head<=tail&&cal(que[tail].p,que[tail].l)<cal(i,que[tail].l))tail--;
if(head>tail)que[++tail]=(node){i,n,i};
else{int t=find(que[tail],i);que[tail].r=t-1;que[++tail]=(node){t,n,i};}
}
F[i]=cal(que[head].p,i);
}
}
int main()
{
n=read();
rep(i,1,n)a[i]=read();
dp(f);
rep(i,1,n/2)swap(a[i],a[n-i+1]);
dp(g);
rep(i,1,n)printf("%d\n",max(0,(int)ceil(max(f[i],g[n-i+1]))));
return 0;
}
