hdu 4521 小明序列（线段树，DP思想）

题意：

①首先定义S为一个有序序列，S={ A1 , A2 , A3 , ... , An }，n为元素个数；
　　②然后定义Sub为S中取出的一个子序列，Sub={ Ai1 , Ai2 , Ai3 , ... , Aim }，m为元素个数；
　　③其中Sub满足 Ai1 < Ai2 < Ai3 < ... < Aij-1 < Aij < Aij+1 < ... < Aim ；
　　④同时Sub满足对于任意相连的两个Aij-1与Aij都有 ij - ij-1 > d (1 < j <= m， d为给定的整数)；
　　⑤显然满足这样的Sub子序列会有许许多多，而在取出的这些子序列Sub中，元素个数最多的称为“小明序列”(即m最大的一个Sub子序列)。
　　例如：序列S={2,1,3,4} ，其中d=1；
　　可得“小明序列”的m=2。即Sub={2,3}或者{2,4}或者{1,4}都是“小明序列”。

　　当小明发明了“小明序列”那一刻,情绪非常激动，以至于头脑凌乱，于是他想请你来帮他算算在给定的S序列以及整数d的情况下，“小明序列”中的元素需要多少个呢？

思路：

DP的思想，但是只能想到N^2的算法。嘿嘿正好题目有说(0<=Ai<=10^5)，那就是了，用线段树保存最值。

每次做题都要考虑周全，边界什么的，，

d=0时单独用贪心的方法算，其实不用也可以，。

代码：

int const N = 100005;

int a[N], f[N];

int F[N<<2];

int n,d;

void PushUp(int rt){

    F[rt]=max( F[rt<<1],F[rt<<1|1] );

    return;

}

void build(int l,int r,int rt){

    if(l==r){

        F[rt]=0;

        return;

    }

    int m=(l+r)>>1;

    build(lson);

    build(rson);

    PushUp(rt);

}

void update(int pos,int x,int l,int r,int rt){

    if(l==r){

        F[rt]=max( F[rt],x );

        return;

    }

    int m=(l+r)>>1;

    if(pos<=m)

        update(pos,x,lson);

    else

        update(pos,x,rson);

    PushUp(rt);

}

int query(int L,int R,int l,int r,int rt){

    if(L<=l && r<=R){

        return F[rt];

    }

    int m=(l+r)>>1;

    int res=0;

    if(L<=m)

        res=max( res,query(L,R,lson) );

    if(m<R)

        res=max( res,query(L,R,rson) );

    return res;

}

int proc1(){

    int d[N];

    int cn=0;

    d[0]=-1;

    rep(i,1,n){

        if(a[i]>d[cn]){

            d[++cn]=a[i];

        }else{

            int pos=lower_bound(d+1,d+1+cn,a[i])-d;

            d[pos]=a[i];

        }

    }

    return cn;

}

int main(){

    while(scanf("%d%d",&n,&d)!=EOF){

        int es=-inf;

        rep(i,1,n){

            scanf("%d",&a[i]);

            es=max( es,a[i] );

        }

        if(d==0){

            int ans=proc1();

            printf("%d\n",ans);

        }else{

            build(0,es,1);

            int ans=1;

            rep(i,1,n){

                if(i-d-1<=0){

                    f[i]=1;

                }else{

                    update(a[i-d-1],f[i-d-1],0,es,1); //pos,x,l,r,rt

                    if(a[i]==0){

                        f[i]=1;

                        continue;

                    }

                    int t=query(0,a[i]-1,0,es,1); //L,R,l,r,rt

                    f[i]=t+1;

                    ans=max( ans,f[i] );

                }

            }

            printf("%d\n",ans);

        }

    }

    return 0;

}

巴特西

hdu 4521 小明序列（线段树，DP思想）

最新文章

热门文章