洛谷 P3928 Sequence

题目描述

小强喜欢数列。有一天，他心血来潮，写下了三个长度均为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.如果在第三行选，对于连续的一段在第三行选的数，必须满足方向相同（都小于等于上一个数或者都大于等于上一个数）

　　清晰版描述简直坑人。。。

　　思路非常明显，智障dp。状态转移方程不读错题的话简直秒出。之后考虑转移优化。显然，一个范围内的最大值可以用线段树维护，当然要事先吧数据离散化。代码很简单，二十分钟就可以敲完，然后我就爆了一个钟的空间23333

#include<bits/stdc++.h>

using namespace std;

#define MAXN 1000000+10

typedef long long LL;

int n,tot=,ans=,pos[][MAXN],dp[][MAXN],tr[][MAXN*];

LL a[][MAXN],b[MAXN*];

void pushup(int t,int k){tr[t][k]=max(tr[t][k<<],tr[t][k<<|]);}

void build(int t,int k,int l,int r){

    tr[t][k]=;

    if(l==r)return;

    int mid=(l+r)>>;

    build(t,k<<,l,mid);

    build(t,k<<|,mid+,r);

}

void update(int t,int k,int l,int r,int p,int val){

    if(l==r&&l==p){

        tr[t][k]=val;

        return;

    }

    int mid=(l+r)>>;

    if(p<=mid)update(t,k<<,l,mid,p,val);

    else update(t,k<<|,mid+,r,p,val);

    pushup(t,k);

}

int query(int t,int k,int l,int r,int L,int R){

    if(l>=L&&r<=R)return tr[t][k];

    int mid=(l+r)>>;

    if(R<=mid)return query(t,k<<,l,mid,L,R);

    else if(L>mid)return query(t,k<<|,mid+,r,L,R);

    else return max(query(t,k<<,l,mid,L,R),query(t,k<<|,mid+,r,L,R));

}

int main(){

    //freopen("data.in","r",stdin);

    scanf("%d",&n);

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

        for(int j=;j<=n;j++){

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

            b[++tot]=a[i][j];

        }

    sort(b+,b+tot+);

    tot=unique(b+,b+tot+)-b,tot--;

    for(int i=;i<=;i++)build(i,,,tot);

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

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

            pos[i][j]=lower_bound(b+,b+tot+,a[i][j])-b;

    for(int i=;i<=;i++)update(i,,,tot,pos[i==?:i][],),dp[i][]=;

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

        for(int k=;k<=;k++)dp[k][i]=;

        for(int k=;k<=;k++){

            if(k==)

                for(int j=;j<=;j++)

                    dp[k][i]=max(dp[k][i],query(j,,,tot,,pos[][i])+);

            else if(k==)

                for(int j=;j<=;j++)

                    dp[k][i]=max(dp[k][i],query(j,,,tot,pos[][i],tot)+);

            else if(k==)

                for(int j=;j<=;j++)

                    dp[k][i]=max(dp[k][i],query(j,,,tot,pos[][i],tot)+);

            else

                for(int j=;j<=;j++)

                    if(j!=)dp[k][i]=max(dp[k][i],query(j,,,tot,,pos[][i])+);

        }

        for(int k=;k<=;k++){

            update(k,,,tot,pos[k==?:k][i],dp[k][i]);

            ans=max(ans,dp[k][i]);

        }

    }

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

    return ;

}

巴特西

洛谷 P3928 Sequence

题目描述

最新文章

热门文章