BZOJ4850/BZOJ2216 JSOI2016灯塔/Poi2011Lightning Conductor（决策单调性）

　　即对每个i最大化h_j-h_i+sqrt(|i-j|)。先把绝对值去掉，正反各做一次即可。注意到当x>y时，sqrt(x+1)-sqrt(x)<sqrt(y+1)-sqrt(y)，所以若对于i选择j比选择k更优(j>k)，对于i+1~n也会是这样，即满足决策单调性（虽然并不能算作dp）。

　　可以这样使用决策单调性优化：维护一个栈，存储当前考虑的这些位置中每个位置向哪个区间转移最优。转移时在栈中二分，然后考虑更新栈，如果新加入的位置向栈顶的整个区间转移都是最优的，直接将栈顶位置弹出，否则二分找一个区间的分割点，最后把这个新位置加入栈中即可。

　　寻找决策区间时小心不要把已更新过的位置算进去。注意维护决策时不能对答案取整，否则会影响决策区间。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,a[N],q[N],l[N],r[N],id[N],top;

double ans[N];

double calc(int i,int j){return a[j]-a[i]+sqrt(i-j);}

void work()

{

    l[]=,r[]=n,id[]=,top=;

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

    {

        int left=,right=top,x;

        while (left<=right)

        {

            int mid=left+right>>;

            if (l[mid]<=i&&r[mid]>=i) {x=mid;break;}

            else if (r[mid]<i) left=mid+;

            else right=mid-;

        }

        ans[i]=max(ans[i],calc(i,id[x]));

        while (top&&l[top]>=i&&calc(l[top],id[top])<calc(l[top],i)) top--;

        left=max(l[top],i),right=r[top],x=r[top]+;

        while (left<=right)

        {

            int mid=left+right>>;

            if (calc(mid,id[top])<calc(mid,i)) x=mid,right=mid-;

            else left=mid+;

        }

        r[top]=x-;

        if (x<=n) top++,l[top]=x,r[top]=n,id[top]=i;

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4850.in","r",stdin);

    freopen("bzoj4850.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

    for (int i=;i<=n;i++) a[i]=read();

    work();reverse(a+,a+n+),reverse(ans+,ans+n+);

    work();for (int i=n;i;i--) printf("%.0f\n",ceil(ans[i]));

    return ;

}

巴特西

BZOJ4850/BZOJ2216 JSOI2016灯塔/Poi2011Lightning Conductor（决策单调性）

最新文章

热门文章