• luogu P3928 SAC E#1


    P3928 SAC E#1 - 一道简单题 Sequence2


    题目背景

    小强和阿米巴是好朋友。


    题目描述

    小强喜欢数列。有一天,他心血来潮,写下了三个长度均为n的数列。

    阿米巴也很喜欢数列。但是他只喜欢其中一种,波动数列。

    阿米巴把他的喜好告诉了小强。小强便打算找出这三个数列内的最长波动数列。

    也就是说,如果我们将三个数列记做a[n][3],他必须要构造一个二元组序列:<p[i], q[i]>,使得对于任何 i>1 有:

    p[i] > p[i-1]

    若q[i] = 0,a[p[i]][q[i]] >= a[p[i-1]][q[i-1]]

    若q[i] = 1,a[p[i]][q[i]] <= a[p[i-1]][q[i-1]]

    若q[i] = 2,只要保持段内同向即可(就是对于连续的一段q[i]=2,要么都有a[p[i]][q[i]] >= a[p[i-1]][q[i-1]],要么都有a[p[i]][q[i]] <= a[p[i-1]][q[i-1]])。

    小强希望这个二元组序列尽可能长。

    提示:当q[i] != q[i-1]时,数列的增减性由q[i]而非q[i-1]决定。

    清晰版题目描述

    小强拿到一个3×n的数组,要在每一列选一个数(或者不选),满足以下条件:

    1.如果在第一行选,那它必须大于等于上一个数

    2.如果在第二行选,那么必须小于等于上一个数

    3.如果在第三行选,对于连续的一段在第三行选的数,必须满足方向相同(都小于等于上一个数或者都大于等于上一个数)


    输入输出格式

    输入格式:

    输入包含4行。

    第一行一个数n,表示数列长度。

    第2、3、4行,每行n个整数,分别表示三个数列。

    输出格式:

    输出仅包含一个整数,即最长波动数列的长度。


    输入输出样例

    输入样例#1:
    6
    1 2 3 6 5 4
    5 4 3 7 8 9
    1 2 3 6 5 4
    
    输出样例#1:
    6

    说明

    对于20%的数据,n <= 10, m <= 1000

    对于60%的数据,n <= 1000, m <= 1000

    对于100%的数据, n <= 100000, m <= 1000000000

    其中m = max|a[i]|

    样例解释:

    取第三行1 2 3(增),然后取第1行6(增),然后取第三行5 4(减),长度为6。


    线段树+dp

    设 dp_(i,k) 表示:第 i 个位置选择第k个序列的数,前 i 个位置 所能构成的最长子序列的长度。

    于是我们有一下4个状态,对于每一个位置i

    k=0选择第一行
    k=1选第二行。
    k=2选第三行,且大于等于前一个数
    k=3选第三行,且小于等于前一个数

    那么根据题意,对于2,3,两个状态,他们不能相互转移.所以我们有

    dp[i][0]=dp[0~i-1][0~3]+1   (a[j][k]<=a[i][0]);
    dp[i][1]=dp[0~i-1][0~3]+1   (a[j][k]>=a[i][1]);
    dp[i][2]=dp[0~i-1][0,1,2]+1   (a[j][k]<=a[i][2]);
    dp[i][3]=dp[0~i-1][0,1,3]+1   (a[j][k]>=a[i][3]);

    那么我们还是发现会T  TAT

    于是就考虑优化第二维j的循环。

    现在对于每一个转移a[i][?]我们都要找到一个dp值最大的a[j][k]其中a[j][k]满足转移;

    于是n很小,就可以把数据离散后放进线段树中.对于dp的每一维建立一个线段树,储存当前以为最后一个选择为(选择数)最大所能到达的dp值。

    bel当前属于第几维的dp(查询&&修改)

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    #define ll long long
    using namespace std;
    const int maxn=100000+233;
    inline int read(){
        int an=0,f=1;
        char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while('0'<=ch&&ch<='9'){an=an*10+ch-'0';ch=getchar();}
        return an*f;
    }
    int dp[maxn][5],n,ans;
    int a[maxn][5],tot,cnt,id[maxn<<2];
    struct saber{
    int ma[6];
    int l,r;
    }tr[maxn<<4];
    void prepare(){
        n=read();
        for(int j=0;j<=2;j++)
            for(int i=1;i<=n;i++){
            a[i][j]=read();tot++;id[tot]=a[i][j];}
        sort(id+1,id+1+tot);
        cnt=unique(id+1,id+1+tot)-id;
        for(int i=1;i<=n;i++)
        for(int j=0;j<=2;j++)
        a[i][j]=lower_bound(id+1,id+cnt,a[i][j])-id+1;
        for(int i=1;i<=n;i++)a[i][3]=a[i][2];
    }
    void build(int k,int l,int r){
        tr[k].l=l;tr[k].r=r;
        if(l==r)return ;
        int mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
    }
    int ask(int bel,int k,int x,int y){
        int l=tr[k].l,r=tr[k].r;
        if(l==x&&r==y)return tr[k].ma[bel];
        int mid=(l+r)>>1;
        if(y<=mid)ask(bel,k<<1,x,y);
        else if(x>mid)ask(bel,k<<1|1,x,y);
        else return max( ask(bel,k<<1,x,mid),ask(bel,k<<1|1,mid+1,y) );
    }
    void add(int bel,int k,int poi,int wi){
        int l=tr[k].l,r=tr[k].r;;
        if(poi==l&&poi==r){
        tr[k].ma[bel]=max(wi,tr[k].ma[bel]);
        return ;}
        int mid=(l+r)>>1;
        if(poi<=mid)add(bel,k<<1,poi,wi);
        else add(bel,k<<1|1,poi,wi);
        tr[k].ma[bel]=max(tr[k<<1].ma[bel],tr[k<<1|1].ma[bel]);
    }
    void DP(){
        build(1,1,cnt);
        for(int i=1;i<=n;i++){
                for(int k=0;k<4;k++){
                dp[i][0]=max(ask(k,1,1,a[i][0])+1,dp[i][0]);//查询小于等于
                dp[i][1]=max(ask(k,1,a[i][1],cnt)+1,dp[i][1]);//后面大于等于
                if(k!=3)
                dp[i][2]=max(ask(k,1,1,a[i][2])+1,dp[i][2]);
                if(k!=2)
                dp[i][3]=max(ask(k,1,a[i][3],cnt)+1,dp[i][3]);
                }
                add(0,1,a[i][0],dp[i][0]);
                add(1,1,a[i][1],dp[i][1]);
                add(2,1,a[i][2],dp[i][2]);
                add(3,1,a[i][3],dp[i][3]);
            }
        for(int i=0;i<4;i++)
        ans=max(ans,dp[n][i]);
    }
    int main(){
        prepare();
        DP();
        cout<<ans;
    }
    Sequence2

    by:s_a_b_e_r


    楼上dalao好厉害,表示我只会树状数组。

    ↑抄自s某一篇题解里的第一句话,接着这个题他就写了个线段树>_< 

    这里补个树状数组的做法

    开4*2个树状数组,表示四种情况*升序/降序

    每次转移升序时查询升序的树状数组里小于a[i][j]的最大dp值

    降序时查询大于a[i][j]的,即在降序树状数组里查询小于n-a[i][j]+1的最大dp值

    每波dp过后记得更新树状数组和答案

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int N=100009,inf=1e9+7;
    int n,a[N][5],b[N<<2],ans;
    int t[N<<2][4][2],cnt,dp[N][5];
    int lowbit(int x){return x&(-x);}
    void add(int x,int v,int p,int q){
        while(x<=cnt)
        {
            t[x][p][q]=max(t[x][p][q],v);
            x+=lowbit(x);
        }
    }
    int ask(int x,int p,int q){
        int re=0;
        while(x)
        {
            re=max(re,t[x][p][q]);
            x-=lowbit(x);
        }
        return re;
    }
    int main()
    {
        scanf("%d",&n);
        for(int k=0;k<3;++k)
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&a[i][k]);
            b[++cnt]=a[i][k];
        }
        for(int i=1;i<=n;++i)a[i][3]=a[i][2];
        sort(b+1,b+cnt+1);
        cnt=unique(b+1,b+cnt+1)-b-1;
        for(int k=0;k<4;++k)
        for(int i=1;i<=n;++i)
            a[i][k]=lower_bound(b+1,b+cnt+1,a[i][k])-b;
        for(int i=1;i<=n;++i){
            for(int k=0;k<4;++k){
                dp[i][0]=max(dp[i][0],ask(a[i][0],k,0)+1);
                dp[i][1]=max(dp[i][1],ask(cnt-a[i][1]+1,k,1)+1);
                if(k!=3)dp[i][2]=max(dp[i][2],ask(a[i][2],k,0)+1);
                if(k!=2)dp[i][3]=max(dp[i][3],ask(cnt-a[i][3]+1,k,1)+1);
            }
            for(int k=0;k<4;++k){
                add(a[i][k],dp[i][k],k,0);
                add(cnt-a[i][k]+1,dp[i][k],k,1);
            }
            ans=max(ans,max(dp[i][0],max(dp[i][1],max(dp[i][2],dp[i][3]))));
        }
        cout<<ans;
        return 0;
    } 
    Sequence2(w)

    by:wypx


  • 相关阅读:
    最快速度找到内存泄漏
    PostMessage与SendMessage各自的问题
    分享一个javascript alert精简框架
    SendMessage、PostMessage原理
    八款常用的 Python GUI 开发框架推荐
    大学学物理将来到底能干什么?
    私有虚函数的特点(C++和Java的机制还有所不同)
    BS与CS的比较
    Eclipse代码自动提示设置
    打印TMemo的内容到打印机
  • 原文地址:https://www.cnblogs.com/ck666/p/7635853.html
一二三 - 开发者的网上家园