hdu 4521 小明系列问题——小明序列

本文从WordPress迁移而来, 查看全部WordPress迁移文章

线段树 dp

题意:略

思考：

  1. 从左至右读入元素并且更新，就可以保证当前这个元素，只受前面的元素影响。
  2. 换一个思路，当前元素为num[i]，由于构建的还是还是LIS，所以在它前面的元素一定要比它小，如果我们能够知道以每个值结尾的LIS就好了，所以用Max[x]表示以x这个值结尾的LIS的最长长度，如果当前要构建以num[i]这个值结尾的LIS，那么只需要在[0,num[i]-1]里面查找到最大的Max[x]即可，但是，找到的这个Max[x]未必是合法的因为,未必距离当前值num[i]的位置大于d，所以采用一种滞后更新的思想，在处理num[i]的时候，这个元素前面d个元素的信息还不能更新，等处理完num[i]再逐一更新
  3. 另外dp[i]记录的是，以序列中第i个元素结尾的LIS的长度，上面提到的Max[i]用一个先单数来维护，具体看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

struct SegTree{
	int l,r,mid,Max;
	SegTree(){}
	SegTree(int _l,int _r,int _M){
		l = _l; r = _r; mid = (l + r) >> 1; Max = _M;
	}
}t[N<<2];
int n,d,Max,num[N],dp[N];

void build(int rt,int a,int b){
	t[rt] = SegTree(a,b,0);
	if(a == b) return ;
	int mid = t[rt].mid;
	build(lson(rt),a,mid);
	build(rson(rt),mid+1,b);
}

void PushUp(int rt){
	t[rt].Max = max(t[lson(rt)].Max,t[rson(rt)].Max);
}

void updata(int rt,int id,int val){
	if(t[rt].l == t[rt].r){
		t[rt].Max = max(t[rt].Max,val);
		return ;
	}
	int mid = t[rt].mid;
	if(id <= mid) updata(lson(rt),id,val);
	else updata(rson(rt),id,val);
	PushUp(rt);
}

int query(int rt,int a ,int b){
	if(t[rt].l == a && t[rt].r == b){
		return t[rt].Max;
	}
	int mid = t[rt].mid;
	if(b <= mid) return query(lson(rt),a,b);
	else if(a > mid) return query(rson(rt),a,b);
	else return max(query(lson(rt),a,mid) , query(rson(rt),mid+1,b));
}

int main(){
	while(scanf("%d%d",&n,&d)!=EOF){
		Max = -1;
		for(int i = 0; i < n ; i++){
			scanf("%d",&num[i]);
			Max = max(Max,num[i]);
		}
		build(1,0,Max);
		int ans = 0;
		cl(dp,0);
		for(int i = 0 ; i < n; i++){
			if(i-d-1 >= 0)
				updata(1,num[i-d-1],dp[i-d-1]);
			if(num[i] == 0) dp[i] = 1;
			else dp[i] = query(1,0,num[i]-1) + 1;
			ans = max(ans,dp[i]);
		}
		printf("%d\n",ans);
	}
	return 0;
}