做网站最贵,个人网店店铺名字,企业邮箱登录入口官网网页版,哪些网站是用php做的题意#xff1a;给你一个序列#xff0c;问相邻两数高度差绝对值小于等于H的子序列有多少个。 dp[i]表示以i为结尾的子序列有多少#xff0c;易知状态转移方程为#xff1a;dp[i] sum( dp[j] ) 1;( abs( height[i] - height[j] ) H ) 由abs( height[i] - height[j] …题意给你一个序列问相邻两数高度差绝对值小于等于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 cstdio2 #include cstring3 #include cstdlib4 #include algorithm5 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 {
19 return x ( -x );
20 }
21
22 int Query( int x )
23 {
24 int res 0;
25 while ( x 0 )
26 {
27 res C[x];
28 res % MOD;
29 x - lowbit(x);
30 }
31 return res;
32 }
33
34 void Add( int x, int v )
35 {
36 while ( x n )
37 {
38 C[x] v;
39 C[x] % MOD;
40 x lowbit(x);
41 }
42 return;
43 }
44
45 int main()
46 {
47 while ( ~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 }
75 return 0;
76 } 转载于:https://www.cnblogs.com/GBRgbr/p/3197983.html
