写了一道单调性优化发现 跟斜率优化很像，而且这道题目感觉质量非常的好。

其实斜率优化是基于单调性优化的，但是面对这道题 我竟然连单调性优化都不太会，尽管这个模型非常不好理解。

对于每道题 我都会打一个暴力 程序一般可得40分左右考试的时候我想时间够的话可以对拍(尽管现在不太会了)。

dp 考虑 f[i]表示第i个数字的最小的p值

f[i]=max(f[i],a[j]-a[i]+sprt(abs(i-j))(向上))其中 j∈[1,n];

将其优化的话第一要先去掉绝对值然后形成两个dp式子

f[i]=max{a[j]-a[i]+sqrt(i-j)}(1<=j<i) f[i]=max{a[j]-a[i]+sqrt(j-i)}(i<j<=n)

发现i j紧紧的连在一起根本不是斜率优化的模型 看完一篇超级不错的题解之后发现是具有单调性的

f[i]=max{a[j]+sqrt(i-j)}-a[i]; 想个办法使得a[j]+sqrt(i-j)最大

发现是单调性优化 get! sqrt(n)的增长速度随n的增大而减小

因为设 j<k<i 如果 a[j]+sqrt(i-j)<a[k]+sqrt(i-k)那么j就被废了 永远都不可能成为最优解

如果 a[j]+sqrt(i-j)>a[k]+sqrt(i-k)那么在某一时刻k会比j优秀 决策就拥有了单调性 单调递增

开一个三元组(p,l,r) p在l 到 r这个区间之中可以取到最优值开心的dp了

const int MAXN=500002;int n;int a[MAXN];db f[MAXN],b[MAXN];struct wy{    int p,l,r;}q[MAXN];inline db max1(db x,db y){
     return x>y?x:y;}inline db calculate(int x,int y){    return db(a[x]+b[abs(y-x)]-a[y]);}inline void swap1(db &x,db &y){db t;t=y;y=x;x=t;return;}inline void swqp(int &x,int &y){
    int t;t=x;y=x;x=t;return;}int ask(wy p,int x){    int l=p.l,r=p.r+1;    while(l+1
      
       >1;        if(calculate(p.p,mid)
       
        q[h].r)h++;        if(h>t||calculate(i,n)>calculate(q[t].p,n))        {            while(h<=t&&calculate(i,q[t].l)>=calculate(q[t].p,q[t].l))--t;            if(h>t)q[++t]=(wy){i,i,n};            else            {                int x=ask(q[t],i);                q[t].r=x-1;                q[++t]=(wy){i,x,n};            }        }        f[i]=max1(f[i],calculate(q[h].p,i));    }}int main(){    //freopen("1.in","r",stdin);    n=read();    for(int i=1;i<=n;i++)a[i]=read(),b[i]=sqrt(1.0*i);    dp();    for(int i=1,j=n;i
        
         =1;i--)put(ceil(f[i]));    return 0;}
        
       
      

这道题目就是比较难一类的 斜率优化需要转换一下问题 至于问题的转换我是看书的因为没想到贪心当时脑子有点乱

看完书上巧妙的转换了问题之后 明白了这竟然是一道比较简单的斜率优化问题！ 2A了（第一次写的是bf）

f[i][j]表示第i个饲养员接走前j个小猫所花费的最小时间

f[i][j]=min(f[i-1][j],f[i-1][k]+t[j]*(j-k)-(s[j]-s[k]));

t数组是 每个接小猫的花费的最小时间  s[k]是前缀和 t[i]=t1[i]-d[i];

然后f[i][j]=min(f[i-1][j],f[i-1][k]+t[j]*(j-k)-(s[j]-s[k]));(1<=k<=j)

此时我处理的是k+1~j的范围内的东西

f[i][j]=min{f[i-1][k]+t[j]*j-t[j]*k-s[j]+s[k]};

f[i][j]=min(f[i-1][k]-t[j]*k+s[k]}+t[j]*j-s[j];

f[i][j]=min(f[i-1][k]+s[k]-t[j]*k};

f[i-1][k]+s[k]=f[i][j]+t[j]*k;

以k为横坐标t[j]为斜率 斜率为定值 我只需让截距f[i][j]最小即可

那么现在t[j]是单调递增的那么维护一个下凸壳就可以...嘿嘿嘿

这么简单的斜率优化问题。成功AC

const int MAXN=100002;int n,m,p;ll d[MAXN],t[MAXN],s[MAXN];ll min(ll x,ll y){
     return x>y?y:x;}ll f[102][MAXN],l,r,q[MAXN];ldb k(ll w,ll x,ll y){
     return (1.0*(f[w-1][x]+s[x]-f[w-1][y]-s[y]))/(1.0*(x-y));}int main(){    //freopen("1.in","r",stdin);    n=read();m=read();p=read();    for(int i=2;i<=n;i++)d[i]=read(),d[i]+=d[i-1];    //for(int i=1;i<=n;i++)cout<
      
       <<' ';puts("");    for(int i=1;i<=m;i++)    {        int x,y;        x=read();y=read();        t[i]=y-d[x];    }    //for(int i=1;i<=m;i++)cout<
       
        <<' '<
        
         =k(i,q[r],j))--r;            q[++r]=j;        }    }    put(f[p][m]);    return 0;}
        
       
      

如果黑洞能吞下一百亿个太阳，我，就是第一百亿零一个太阳。