|
|
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3349
  /**//*
 题意：
给定一个d(0 <= d <= 10^8)和(N <= 10^5)的数列，求最长的特殊子序列，
所谓特殊子序列就是相邻元素之间的绝对值之差小于等于d。
解法：
动态规划+线段树
思路：
这题又是一个动态规划，状态转移方程很容易想到：
dp[ val[i] ] = 1 + max( dp[ val[i] - d ]  dp[ val[i] + d ] )
dp[j] 表示以j为止的最长特殊子序列的值，这样就可以维护一个区间，每次
查询和当前数绝对值差小于等于d的数组成的区间，将最大值+1更新到当前数
对应的位置上，利用线段树每次更新和查询都是log(n)。
 */
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 600010
int n, d;
int val[maxn];
struct Tree {
int Max;
int son[2];
  void clear() {
son[0] = son[1] = -1;
Max = 0;
 }
}T[maxn*4];
int tot;
int Max(int a, int b) {
return a > b ? a : b;
}
int Min(int a, int b) {
return a < b ? a : b;
}
void Query(int root, int nx, int ny, int l, int r, int& ans) {
if(nx > r || ny < l || root == -1 || T[root].Max <= ans)
return ;
if(nx <= l && r <= ny) {
ans = Max(ans, T[root].Max);
return ;
}
int mid = (l + r) >> 1;
Query(T[root].son[0], nx, ny, l, mid, ans);
Query(T[root].son[1], nx, ny, mid+1, r, ans);
}
void Insert(int& root, int nPos, int l, int r, int val) {
if(nPos < l || nPos > r)
return ;
if(root == -1) {
root = tot++;
T[root].clear();
}
T[root].Max = Max(val, T[root].Max);
if(l == nPos && nPos == r) {
return ;
}
int mid = (l + r) >> 1;
Insert(T[root].son[0], nPos, l, mid, val);
Insert(T[root].son[1], nPos, mid+1, r, val);
}
int main() {
int i;
int MMin, MMax;
while(scanf("%d %d", &n, &d) != EOF) {
for(i = 0; i < n; i++) {
scanf("%d", &val[i]);
if(i) {
MMin = Min(MMin, val[i]);
MMax = Max(MMax, val[i]);
}else {
MMin = val[i];
MMax = val[i];
}
}
tot = 0;
int root = -1;
int ans = 1;
for(i = 0; i < n; i++) {
int l = (val[i] - d) < MMin ? MMin : (val[i] - d);
int r = (val[i] + d) > MMax ? MMax : (val[i] + d);
int MM = 0;
Query(root, l, r, MMin, MMax, MM);
Insert(root, val[i], MMin, MMax, MM + 1);
if(MM + 1 > ans)
ans = MM + 1;
}
printf("%d\n", ans);
}
return 0;
}
|