题意：给你一个序列，问相邻两数高度差绝对值小于等于H的子序列有多少个。
dp[i]表示以i为结尾的子序列有多少，易知状态转移方程为：dp[i] = sum( dp[j] ) + 1;( abs( height[i] - height[j] ) <= H )
由abs( height[i] - height[j] ) <= H 可得height[i] - H <= height[j] <= height[i] + H
将序列中的数离散化，每个height对应一个id, 用树状数组求区间[height[i] - H的id, height[i] + H的id ]内dp[j]的和，并且每次把新得到的dp[i]更新到树状数组中height[i]的id对应的位置。
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int MAXN = 100100; 9 const int MOD = 9901;10 11 int dp[MAXN];12 int height[MAXN];13 int num[MAXN];14 int C[MAXN];15 int n, d;16 17 int lowbit( int x )18 {19return x & ( -x );20 }21 22 int Query( int x )23 {24int res = 0;25while ( x > 0 )26{27 res += C[x];28 res %= MOD;29 x -= lowbit(x);30}31return res;32 }33 34 void Add( int x, int v )35 {36while ( x <= n )37{38 C[x] += v;39 C[x] %= MOD;40 x += lowbit(x);41}42return;43 }44 45 int main()46 {47while ( ~scanf( "%d%d", &n, &d ) )48{49 for ( int i = 1; i <= n; ++i )50 {51 scanf( "%d", &height[i] );52 num[i] = height[i];53 }54 55 sort( num + 1, num + n + 1 );56 int cnt = unique( num + 1, num + n + 1 ) - num - 1;57 58 memset( C, 0, sizeof(C) );59 int ans = 0;60 dp[0] = 0;61 for ( int i = 1; i <= n; ++i )62 {63 int id = lower_bound( num + 1, num + cnt + 1, height[i] ) - num;64 int left = lower_bound( num + 1, num + cnt + 1, height[i] - d ) - num;65 int right = upper_bound( num + 1, num + cnt + 1, height[i] + d ) - num - 1;66 dp[i] = ( Query( right ) - Query( left - 1 ) + 1 ) % MOD;67 ans += dp[i];68 Add( id, dp[i] );69 }70 71 if ( ans >= n ) ans -= n;72 else ans = 0;73 printf("%d\n", ans % MOD );74}75return 0;76 }
