|
|
題目鏈接：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;
}
|