题意：已知一个长度为 n 的序列 a。对于每个 1<=i<=n，找到最小的非负整数 p 满足 对于任意的 j, aj < = ai + p - sqrt(abs(i-j))
已经懒到不想打数学公式了...
差不多是第一次写这种决策单调性的题，怎么弱成这个样子啊... 所以写的详细一点。
首先取绝对值很烦，显然我们可以正反各做一遍，拿掉绝对值。
令 \(f_i=max(a_j+\sqrt{i-j})-a_i\)
把这个看成 dp，则满足如下性质：
对于本层（本题只有一层）dp，求一点的 dp 值与同层其他点均无关。（显然得证）
令\(f_i\) 的决策点为\(opt_i\)，则一定有\(opt_1\leq opt_2\leq ...\leq opt_n\)（证明非常简单，考虑一个 opt_{i} > opt_{i+1} 的情况，显然不成立）
那么我们可以分治优化这层的 dp 过程，每次维护可能取值的区间，取出 mid 切割区间即可，\(log_n\) 层，每层\(O(n)\)，复杂度\(O(nlog_n)\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 500005 #define ll long long using namespace std; #define fstc __attribute__((optimize("-O3"))) #define IL __inline__ __attribute__((always_inline)) inline int read() { int x=0,f=1;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; } #define OUT 5000000 char Out[OUT],*ou=Out; int Outn[30],Outcnt; inline void write(int x) { if(!x)*ou++=48; else { for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48; while(Outcnt)*ou++=Outn[Outcnt--]; } } double f[N],g[N]; int n,a[N]; void solve(double *f,int l,int r,int L,int R) { if(l>r)return ; int mid=(l+r)>>1,pos=0; for(int i=L;i<=R;i++) if(a[i]+sqrt(mid-i)>f[mid])f[mid]=a[i]+sqrt(mid-i),pos=i; f[mid]-=a[mid]; if(l!=r) solve(f,l,mid,L,pos),solve(f,mid+1,r,pos,R); } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); solve(f,1,n,1,n); reverse(a+1,a+n+1); solve(g,1,n,1,n); reverse(g+1,g+n+1); for(int i=1;i<=n;i++) { double ret=max(f[i],g[i]); int tmp=ret; if(tmp!=ret)tmp++; write(tmp),*ou++='\n'; } fwrite(Out,1,ou-Out,stdout); } |
Comments | NOTHING