P3515 [POI2011]Lightning Conductor[决策单调性优化]

给定一序列，求对于每一个$a_i$的最小非负整数$p_i$，使得$\forall j \neq i $有$ p_i>=a_j-a_i+ \sqrt{|i-j|}$。

绝对值很烦，先分左右情况单独做。现在假设j都在i左边，则$ p_{i} = max \{ a_{j}-a_{i}+ \sqrt{i-j} \} = max \{ a_{j}+ \sqrt{i-j} \} - a_i$。带根号，不易斜率优化，考虑证决策单调性。

假设最优决策为j，j之前的任意决策称之为$j'$,只与$j$有关的项令之为$h[j]=a[j]$,则有

$h[j]+\sqrt{i-j} \geqslant h[j']+\sqrt{i-j'}$ ①

现要证$ h[j]+\sqrt{i-j+1} \geqslant h[j']+\sqrt{i-j'+1}$ ②

即证$ \sqrt{i-j+1}-\sqrt{i-j} \geqslant \sqrt{i-j'+1}-\sqrt{i-j'}$（$②-①$得）

那么把它看成关于$j$的函数看单调性，设$g(j)=\sqrt{i-j+1}+\sqrt{i-j}$

对其求导。

$g'(j)=[(i-j+1)^{\frac{1}{2}}]' - [(i-j)^{\frac{1}{2}}]'=-\frac{1}{2} (i-j+1)^{-\frac{1}{2}} + \frac{1}{2} (i-j)^{-\frac{1}{2}}=\frac{1}{2} (\frac{1}{\sqrt{i-j}}-\frac{1}{\sqrt{i-j+1}})$

由$ i-j<i-j+1$知$\frac{1}{2} (\frac{1}{\sqrt{i-j}}-\frac{1}{\sqrt{i-j+1}}) > 0$则函数$g(j)$单调增，则上不等式成立，满足单调性。

证完决策单调性优化即可。

错误记录：第二次写的时候line37写成l<r了，，丢人。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef double db;

 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}

 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=+;

 struct kochiya_sanae{

     int l,r,pos;

     kochiya_sanae(int l0=,int r0=,int pos0=):l(l0),r(r0),pos(pos0){}

 }q[N];

 db sq[N],f[N],h[N];

 int n,l,r;

 inline void preprocess(){for(register int i=;i<=n;++i)sq[i]=sqrt((db)i);}

 inline db calc(int j,int i){return (db)h[j]+sq[i-j];}

 inline int find_pos(int L,int R,int j,int i){

     ++R;int mid;

     while(L<R){

         mid=L+R>>;

         if(calc(j,mid)<=calc(i,mid))R=mid;

         else L=mid+;

     }

     return R;

 }

 inline void dp(){

     q[l=r=]=kochiya_sanae(,n,);

     for(register int i=;i<=n;++i){

         if(q[l].r<i)++l;else ++q[l].l;

         MAX(f[i],calc(q[l].pos,i)-h[i]);

         while(l<=r&&calc(q[r].pos,q[r].l)<=calc(i,q[r].l))--r;

         if(r<l)q[r=l]=kochiya_sanae(i,n,i);

         else{

             int k;

             if(calc(q[r].pos,q[r].r)>calc(i,q[r].r))k=q[r].r+;

             else k=find_pos(q[r].l,q[r].r,q[r].pos,i);

             if(k<=n)q[r].r=k-,q[++r]=kochiya_sanae(k,n,i);

         }

     }

 }

 int main(){//freopen("tmp.in","r",stdin);freopen("tmp.out","w",stdout);

     read(n);for(register int i=;i<=n;++i)read(h[i]);h[]=-;

     preprocess();dp();reverse(h+,h+n+);reverse(f+,f+n+);dp();

     for(register int i=n;i;--i)printf("%d\n",(int)ceil(f[i]));

     return ;

 }

巴特西

P3515 [POI2011]Lightning Conductor[决策单调性优化]

最新文章

热门文章