做题时间：2022.10.14
\(【题目描述】\)
给定一个长度为 \(n(n\leq 5\times 10^5)\) 的非负整数序列 \(a(a_i\leq 10^9)\)，对于 \(\forall i\in[1,n]\)，求出最小的非负整数 \(p\)，使得对于 \(\forall j\in[1,n]\)，均满足 \(a_j\leq a_i+p-\sqrt{|i-j|}\)
\(【输入格式】\)
第一行一个整数 \(n\)
接下来 \(n\) 行每行一个整数表示序列 \(a\)
\(【输出格式】\)
一行一个整数表示答案
\(【考点】\)
决策单调性优化dp
\(【做法】\)
令 \(f_i\) 表示 \(i\) 的答案，有：
\[f_{i}\geq a_j-a_i+\sqrt{|i-j|} \]求最小的 \(f\)，即：
\[f_{i}=\max\limits_{j=1}^n( a_j+\lceil\sqrt{|i-j|}\rceil)-a_i \]\(j\) 的范围使得不能直接分治解决，因此拆开：
\[\left\{ \begin{aligned} f_{i}=\max\limits_{j=1}^{i-1}(a_j+\lceil \sqrt{i-j} \rceil)-a_i\\ f_i=\max\limits_{j=i}^n(a_j+\lceil \sqrt{j-i} \rceil)-a_i \end{aligned} \right. \]分开求解即可。
这便是基于分支的决策单调性优化dp的模板了。
#include<cstdio>
#include<iomanip>
#include<cmath>
#define int long long
using namespace std;
typedef long long ll;
const int N=5e5+50,inf=1e9;
int a[N];
long double f[2][N];
int n;
inline long double calc(int l,int r)
{
return a[l]+sqrt(abs(l-r));
}
void dp(int l,int r,int jl,int jr,int p)
{
if(r<l) return ;
int mid=(l+r)>>1;
int num=mid,st,ed;
if(p) st=jl,ed=min(jr,mid);
else st=max(jl,mid),ed=jr;
f[p][mid]=(long double)a[mid];
for(int i=st;i<=ed;i++){
if(calc(i,mid)>f[p][mid]){
f[p][mid]=calc(i,mid),num=i;
}
}
f[p][mid]-=(long double)a[mid];
dp(l,mid-1,jl,num,p);
dp(mid+1,r,num,jr,p);
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
dp(1,n,1,n,0);//分开求解
dp(1,n,1,n,1);
for(int i=1;i<=n;i++) printf("%lld\n",(long long)ceil(max(f[0][i],f[1][i])));
return 0;
}