题目1413：神秘元素 ——lis的元素是否唯一

求序列的最长子序列中不可分割元素的数目。不可分割元素，肯定属于某一个最长子序列，首先做的就是把属于最长子序列的数提取出来，减小查找范围。怎么提取？可以用LIS（最长递增子序列）和LDS（最长递减子序列）。对序列，从前往后，求以每个数 a[i] 为底最长子序列数组index。从后往前，求以每个数a[i]为底的最长递减子序列数组index2。线扫一遍，如果index[i] + index2[i] == length+1(length表示最长子序列的长度)，那么这个数就是属于某一个最长子序列的。

　　提取出来以后，对每个数a[i]，看它所对应的index1[i] 在整个数组中出现几次，如果只出现一次，那么表示这个数是不可分割元素。最后输出！

#include<stdio.h>

const int MAXN=;

int n,a[MAXN],s[MAXN],index[MAXN];//序列存在s里

int lis()//单调降子序列nlogn算法

{

    int l,r,mid,len=;

    a[]=s[];

    index[]=;

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

    {

        l=,r=len;

        while(l<=r)

        {

            mid=(l+r)>>;//除2

            if(a[mid]<s[i]) l=mid+;//不降

            else r=mid-;//二分查找

        }

        a[l]=s[i];//插入

        index[i]=l;

        if(l>len) len++;//增加长度

    }

    return len;

}

int s2[MAXN],index2[MAXN];//序列存在s2里

int lis2()//单调不升子序列nlogn算法

{

    int l,r,mid,len=;

    a[]=s2[];

    index2[]=;

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

    {

        l=,r=len;

        while(l<=r)

        {

            mid=(l+r)>>;//除2

            if(a[mid]>s2[i]) l=mid+;//升

            else r=mid-;//二分查找

        }

        a[l]=s2[i];//插入

        index2[i]=l;

        if(l>len) len++;//增加长度

    }

    return len;

}

int hash[MAXN];

int main(){

    int i;

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

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

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

            s2[n-i+]=s[i];

            hash[i]=;

        }

        int len=lis();

        lis2();

        int add=;

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

            if(index[i]+index2[n-i+]==(len+)){

                hash[index[i]]++;

            }

        }

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

            if(hash[i]==)add++;

        }

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

    }

}

巴特西

题目1413：神秘元素 ——lis的元素是否唯一

最新文章

热门文章