zoj 3349 dp + 线段树优化

题目:给出一个序列,找出一个最长的子序列,相邻的两个数的差在d以内。

 /*
线段树优化dp
dp[i]表示前i个数的最长为多少,则dp[i]=max(dp[j]+1) abs(a[i]-a[j])<=d
复杂度为O(n ^ 2)
利用线段树优化,线段树保存区间最大值。离散化后便可求出,还要注意 对于叶子节点保存的即为dp的值,每次更改即可,开始一直累加。。。。。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm> using namespace std;
#define lson l,m,rt<<1
#define rson m + 1, r, rt<<1|1
const int maxn = 1e5 + ;
int s[maxn];
int n, d;
int san[maxn], tot;
int sum[maxn << ];
void pushUp(int rt){
sum[rt] = max(sum[rt<<], sum[rt<<|]);
}
void update(int pos, int c, int l, int r, int rt){
if (l == r){
sum[rt] = c;//注意
return ;
}
int m = (l + r) >> ;
if (pos <= m) update(pos, c, lson);
else update(pos, c, rson);
pushUp(rt);
}
int query(int L, int R, int l, int r, int rt){
if (L <= l && R >= r){
return sum[rt];
}
int m = (l + r) >> ;
int ret = ;
if (L <= m) ret = query(L, R, lson);
if (R > m) ret = max(ret, query(L, R, rson));
return ret;
}
int main(){
while (~scanf("%d%d", &n, &d)){
tot = ;
for (int i = ; i <= n; ++i){
scanf("%d", &s[i]);
san[tot++] = s[i];
}
sort(san, san + tot);
tot = unique(san, san + tot) - san; memset(sum, , sizeof(sum));
int ans = ;
for (int i = ; i <= n; ++i){
int pos = lower_bound(san, san + tot, s[i]) - san + ;
int l = lower_bound(san, san + tot, s[i] - d) - san + ;
int r = upper_bound(san, san + tot, s[i] + d) - san;
int que = query(l, r, , tot, ) + ;
//cout << " l = " << l << " r = " << r << endl;
ans = max(ans, que);
//cout << " ans = " << ans << endl;
update(pos, que, , tot, );
}
printf("%d\n", ans);
}
return ;
}
上一篇:在linux下,怎么去查看一个运行中的程序, 到底是占用了多少内存


下一篇:SQL 必知必会·笔记<7>汇总数据——使用聚合函数