洛谷3928 一道简单题

标签：DP，线段树，数据结构

清晰版题目描述

小强拿到一个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裸题，设f[i][1/2/3/4]分别表示取前i列数中以第1/2/3/4行结尾的最长波动数列长度

F[i][1]=max(f[j][1/2/3/4]+1)  j<i 且a[j][1/2/3/4]<=a[i][1]

剩下三行的转移同理，这种做法时间复杂度为O（n^2）

满分的做法可以直接用线段树维护

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=1e5+6;
int n,cnt=0,ans=0;
int a[maxn],b[maxn],c[maxn],num[maxn<<4],f[maxn][5],tree[maxn<<4][5];
void insert(int id,int rt,int l,int r,int pos,int v){
	if(l==r){tree[rt][id]=max(tree[rt][id],v);return;}
	int mid=(l+r)>>1;
	if(pos<=mid)insert(id,rt<<1,l,mid,pos,v);
	else insert(id,rt<<1|1,mid+1,r,pos,v);
	tree[rt][id]=max(tree[rt<<1][id],tree[rt<<1|1][id]);
}
int query(int id,int rt,int l,int r,int L,int R){
	if(L<=l&&r<=R)return tree[rt][id];
	int mid=(l+r)>>1,ans=0;
	if(L<=mid)ans=max(ans,query(id,rt<<1,l,mid,L,R));
	if(mid+1<=R)ans=max(ans,query(id,rt<<1|1,mid+1,r,L,R));
	return ans;
}

int main()
{
	n=read();
	rep(i,1,n)a[i]=read(),num[++cnt]=a[i];
	rep(i,1,n)b[i]=read(),num[++cnt]=b[i];
	rep(i,1,n)c[i]=read(),num[++cnt]=c[i];
	sort(num+1,num+1+cnt);
	cnt=unique(num+1,num+cnt+1)-num-1;
	rep(i,1,n)a[i]=lower_bound(num+1,num+cnt+1,a[i])-num;
	rep(i,1,n)b[i]=lower_bound(num+1,num+cnt+1,b[i])-num;
	rep(i,1,n)c[i]=lower_bound(num+1,num+cnt+1,c[i])-num;
	rep(i,1,n){
		f[i][1]=max(f[i][1],query(1,1,1,cnt,1,a[i]));
		f[i][1]=max(f[i][1],query(2,1,1,cnt,1,a[i]));
		f[i][1]=max(f[i][1],query(3,1,1,cnt,1,a[i]));
		f[i][1]=max(f[i][1],query(4,1,1,cnt,1,a[i]));
		f[i][1]++;
		f[i][2]=max(f[i][2],query(1,1,1,cnt,b[i],cnt));
		f[i][2]=max(f[i][2],query(2,1,1,cnt,b[i],cnt));
		f[i][2]=max(f[i][2],query(3,1,1,cnt,b[i],cnt));
		f[i][2]=max(f[i][2],query(4,1,1,cnt,b[i],cnt));
		f[i][2]++;
		f[i][3]=max(f[i][3],query(1,1,1,cnt,1,c[i]));
	    f[i][3]=max(f[i][3],query(2,1,1,cnt,1,c[i]));
		f[i][3]=max(f[i][3],query(3,1,1,cnt,1,c[i]));
		f[i][3]++;
		f[i][4]=max(f[i][4],query(1,1,1,cnt,c[i],cnt));
		f[i][4]=max(f[i][4],query(2,1,1,cnt,c[i],cnt));
		f[i][4]=max(f[i][4],query(4,1,1,cnt,c[i],cnt));
		f[i][4]++;
		insert(1,1,1,cnt,a[i],f[i][1]);
		insert(2,1,1,cnt,b[i],f[i][2]);
		insert(3,1,1,cnt,c[i],f[i][3]);
		insert(4,1,1,cnt,c[i],f[i][4]);
	}
	rep(i,1,n)
	    rep(j,1,4)ans=max(ans,f[i][j]);
	printf("%d\n",ans);
	return 0;
}