hdu 4521 小明系列问题——小明序列(线段树 or DP)

时间:2022-07-20 21:05:48

  题目链接:hdu 4521

  本是 dp 的变形,却能用线段树,感觉好强大。

  由于 n 有 10^5,用普通的 dp,算法时间复杂度为 O(n2),肯定会超时。所以用线段树进行优化。线段树维护的是区间内包含某点的最大满足条件的长度,叶子节点以该元素结尾,最长长度。至于相邻两项隔 d 个位置,求 dp[i] 时,我们只把 dp[i - d - 1] 更新至线段树中,然后在这颗线段树中找最大的个数。

  具体来说,就是把序列 S 的值 Ai 作为线段树叶子下标,以 Ai 结尾的 LIS 长度(即经典算法里的 dp[i])作为叶子结点的值,然后对每个 Ai,查询 0 ~ Ai - 1 的最大的 LIS 长度(也就是 dp[]),这个用线段树实现可以很快地得到结果;至于更新时,不能每遍历到一个就直接更新,因为这样子的话 A[i - d] ~ A[i - 1] 会被加入到线段树中,它们对 A[i] 无任何作用,却会对线段树的查询结果有干扰,因此我们在对每一个 Ai 进行查询(即计算出对应的 dp[i])前,就只把 A[i - d - 1] 即 dp[i - d - 1] 加入到线段树中即可,这个操作是很关键的。理清思路后,就是线段树的单点更新、区间查询了。

  因为我写线段树习惯从 1 开始,所以对所有元素都 +1 了。

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define root int rt, int l, int r
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define makemid int mid = l + r >> 1
const int N = ; int len[N << ]; void build(root) {
len[rt] = ;
if(l == r) return ;
makemid;
build(lson);
build(rson);
} inline void pushup(int rt) {
len[rt] = max(len[rt << ], len[rt << | ]);
} int pos, val;
void update(root) {
if(l == r) {
len[rt] = max(len[rt], val);
return ;
}
makemid;
if(pos <= mid) update(lson);
else update(rson);
pushup(rt);
} int ql,qr;
int query(root) {
if(ql <= l && r <= qr) return len[rt];
makemid;
int res = ;
if(ql <= mid) res = max(res, query(lson));
if(qr > mid) res = max(res, query(rson));
return res;
} int dp[N], num[N]; int main() {
int n,d;
while(~scanf("%d%d",&n,&d)) {
int mm = , ans = ;
for(int i = ; i <= n; ++i) {
scanf("%d",num + i);
++num[i];
mm = max(mm, num[i]);
}
build(,,mm);
for(int i = ; i <= n; ++i) {
if(i - d - >= ) { //这是关键,只把 i-d-1 前面的更新至线段树中
pos = num[i - d - ];
val = dp[i - d - ];
update(,,mm);
}
if(num[i] == ) dp[i] = ;
else {
ql = ;
qr = num[i] - ;
dp[i] = query(,,mm) + ;
}
ans = max(ans, dp[i]);
}
printf("%d\n",ans);
}
return ;
}