Description

已知一个长度为n的序列\(a_1,a_2,...,a_n\)。

对于每个\(1\leq i\leq n\)，找到最小的非负整数\(p\)满足 对于任意的\(j\), \(a_j \leq a_i + p - \sqrt{abs(i-j)}\)

Solution

去掉\(abs\)容易，前后各扫一遍就可以了。

\(f[i]=max(num[j]-num[i]+\sqrt{i-j})\)

函数\(f(x)=\sqrt x\)的增长率越来越慢

如果当前最优转移为\(k\)，可知之后的最优转移必然\(>=k\)

---

这题是决策单调性的题目。

决策单调性的核心是利用决策点单调的性质，维护一个决策点的队列，满足任何时候后面的点都不优于前面的点，否则就把队首的元素pop掉，用二分就可以算出一个点优于前一个点时间，显然这个时间是应该单增的。

Code 

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))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<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 500005int n,a[MN],t[MN];double f[MN],sq[MN];int l,r,q[MN];inline void rw(double &x,double y){if(y>x) x=y;}inline double calc(int T,int x){return a[x]+sq[T-x];}inline int get(int x,int y){    int l=y,r=n,mid,ans=n+1;    while(l<=r)    {        mid=(l+r)>>1;        if(calc(mid,x)<=calc(mid,y)) ans=mid,r=mid-1;        else l=mid+1;    }    return ans;}int main(){    n=read();    register int i;    for(i=1;i<=n;++i) a[i]=read(),f[i]=0.;    for(i=1;i<=n;++i) sq[i]=sqrt((double)i);    for(l=1,r=0,i=1;i<=n;++i)    {        for(;l
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！