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;
}