ZOJ 3349 Special Subsequence 简单DP + 线段树

同 HDU 2836 只不过改成了求最长子串。
DP+线段树单点修改+区间查最值。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 
 6 #define lson l, m, rt << 1
 7 #define rson m + 1, r, rt << 1 | 1
 8 
 9 using namespace std;
10 
11 const int MAXN = 100100;
12 
13 int n, d;
14 int val[MAXN];
15 int num[MAXN];
16 int dp[MAXN];
17 
18 int maxi[ MAXN << 2 ];
19 
20 void pushUp( int rt )
21 {
22     maxi[rt] = max( maxi[rt << 1], maxi[rt << 1 | 1] );
23     return;
24 }
25 
26 void Update( int L, int c, int l, int r, int rt )
27 {
28     if ( l == L && L == r )
29     {
30         maxi[rt] = c;
31         return;
32     }
33 
34     int m = ( l + r ) >> 1;
35     if ( L <= m ) Update( L, c, lson );
36     else Update( L, c, rson );
37     pushUp( rt );
38     return;
39 }
40 
41 int Query( int L, int R, int l, int r, int rt )
42 {
43     if ( L <= l && r <= R )
44         return maxi[rt];
45 
46     int m = ( l + r ) >> 1;
47 
48     int res = 0;
49     if ( L <= m ) res = max( res, Query( L, R, lson ) );
50     if ( R > m )  res = max( res, Query( L, R, rson ) );
51 
52     return res;
53 }
54 
55 int main()
56 {
57     while ( ~scanf( "%d%d", &n, &d ) )
58     {
59         for ( int i = 1; i <= n; ++i )
60         {
61             scanf( "%d", &val[i] );
62             num[i] = val[i];
63         }
64 
65         sort( num + 1, num + 1 + n );
66         int cnt = unique( num + 1, num + n + 1 ) - num - 1;
67 
68         dp[0] = 0;
69         memset( maxi, 0, sizeof(maxi) );
70         int ans = 0;
71 
72         for ( int i = 1; i <= n; ++i )
73         {
74             int id = lower_bound( num + 1, num + cnt + 1, val[i] ) - num;
75             int left = lower_bound( num + 1, num + cnt + 1, val[i] - d ) - num;
76             int right = upper_bound( num + 1, num + cnt + 1, val[i] + d ) - num - 1;
77             dp[i] = Query( left, right, 1, n, 1 ) + 1;
78             ans = max( ans, dp[i] );
79             Update( id, dp[i], 1, n, 1 );
80         }
81         printf( "%d
", ans );
82     }
83     return 0;
84 }