首页 > 代码库 > ZOJ3349——Special Subsequence
ZOJ3349——Special Subsequence
There a sequence S with n integers , and A is a special subsequence thatsatisfies |Ai-Ai-1| <=d ( 0 <i<=|A|))
Now your task is to find the longest special subsequence of a certain sequenceS
Input
There are no more than 15 cases , process till the end-of-file
The first line of each case contains two integer n and d ( 1<=n<=100000 ,0<=d<=100000000) as in the description.
The second line contains exact n integers , which consist the sequneceS .Eachinteger is in the range [0,100000000] .There is blank between each integer.
There is a blank line between two cases
Output
For each case , print the maximum length of special subsequence you can get.
Sample Input
5 2 1 4 3 6 5 5 0 1 2 3 4 5
Sample Output
3 1
水dp+水线段树
哈哈今天的第一个1Y
#include <map> #include <set> #include <list> #include <queue> #include <stack> #include <vector> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 100010; int dp[N], xis[N], arr[N]; int n, d, cnt; struct node { int l, r; int val; }tree[N << 2]; int BinSearch(int x) { int l = 1, r = cnt, mid; while (l <= r) { mid = (l + r) >> 1; if (xis[mid] > x) { r = mid - 1; } else if (xis[mid] < x) { l = mid + 1; } else { break; } } return mid; } int left_binsearch(int x) { int l = 1, r = cnt, mid, ans = -1; while (l <= r) { mid = (l + r) >>1; if (xis[mid] >= x) { ans = mid; r = mid - 1; } else { l = mid + 1; } } return ans; } int right_binsearch(int x) { int l = 1, r = cnt, mid, ans = -1; while (l <= r) { mid = (l + r) >>1; if (xis[mid] <= x) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans; } void build(int p, int l, int r) { tree[p].l = l; tree[p].r = r; tree[p].val = -1; if (l == r) { return; } int mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); } void update(int p, int pos, int val) { if (tree[p].l == tree[p].r) { tree[p].val = max(tree[p].val, val); return; } int mid = (tree[p].l + tree[p].r) >> 1; if (pos <= mid) { update(p << 1, pos, val); } else { update(p << 1 | 1, pos, val); } tree[p].val = max(tree[p << 1].val, tree[p << 1 | 1].val); } int query(int p, int l, int r) { if (l <= tree[p].l && r >= tree[p].r) { return tree[p].val; } int mid = (tree[p].l + tree[p].r) >> 1; if (r <= mid) { return query(p << 1, l, r); } else if (l > mid) { return query(p << 1 | 1, l, r); } else { return max(query(p << 1, l, mid), query(p << 1 | 1, mid + 1, r)); } } int main() { while(~scanf("%d%d", &n, &d)) { cnt = 0; int ans = 0; memset (dp, 0, sizeof(dp)); for (int i = 1; i <= n; ++i) { scanf("%d", &arr[i]); xis[++cnt] = arr[i]; } sort (xis + 1, xis + cnt + 1); cnt = unique(xis + 1, xis + cnt + 1) - xis - 1; build(1, 1, cnt); for (int i = 1; i <= n; ++i) { int cur = BinSearch(arr[i]); int l = left_binsearch(arr[i] - d); int r = right_binsearch(arr[i] + d); if (l < 0) { l = 1; } if (r < 0) { r = cnt; } int tmp = query(1, l, r); if (tmp == -1) { dp[i] = 1; } else { dp[i] = tmp + 1; } update(1, cur, dp[i]); ans = max(ans, dp[i]); } printf("%d\n", ans); } return 0; }
ZOJ3349——Special Subsequence