[原创]HDU 2836 Traversal [树状数组+二分+dp]【数据结构】

2016-11-10 16:24:18 Tabris_ 阅读数：269

博客爬取于2020-06-14 22:42:40
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/53116979

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2836
----------------------------------------------------------------------------------.
Traversal

Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 891 Accepted Submission(s): 348

Problem Description
I arrive at a big lake and I have to cross it. Luckily, I’m a very good jumper, but the lake is too big to be crossed in one jump. On the shore, I find N boxes of different heights, set in a certain order. If I throw a box into the lake, it will float and it will have the same height as on the shore. This is good, because I intend to throw some boxes into the lake and get from one shore to the other by jumping from box to box. The only things to consider are:
The lake is big, so I must throw at least 2 boxes, which means that in order to cross the lake I have to make at least 3 jumps.
Not all the boxes have to be thrown; some of them may be ignored.
The boxes can be thrown into the lake only in the order they are found on the shore and I have to jump on them in this order.
The height difference between two consecutive boxes I use must be at most H meters, because I can jump a lot in length, but I have some problems with jumping in height.The height of a box doesn’t change when I jump on it.
I’m always able to jump from the shore to a box and from a box to the shore, no matter what the height of the box is.

Facing so many possibilities that respect the above conditions, I begin counting the number of possibilities that I have, instead of actually crossing the lake. I quickly find the answer and I wonder whether you can also find it as fast as I did.

Task

Write a program that determines the number of possibilities to cross the lake in the above conditions. Since the number can be quite big, you only have to output the remainder of this number, when divided by 9901.

Input
There are multiple test cases. Each test case contains two integers N and H, separated by a space, representing the number of boxes and the maximum height difference between two consecutive boxes thrown into the lake. The following N lines contain the heights of the boxes, in the order the boxes are set on the shore. The (i+1)th line contains the height of the ith box.

Output
For each test case you should output a single line, containing the number of possibilities modulo 9901.

Constraints

1 < N < 100 001
0 < H < 100 000 001
The height of any box is a strictly positive integer and does not exceed 100 000 000

Sample Input
4 2
1
3
7
5

Sample Output
4

Hint

Explanation

There are 4 possibilities:
1 3
1 3 5
3 5
7 5

Source
2009 Multi-University Training Contest 3 - Host by WHU

------------------------------------------------------------------------------------.
题目大意：
就是给你一个序列,至少选出两个元素的序列中使得相邻元素之间的差≤h 的方案数。

解题思路：
首先不看数据范围的话，很好想了 ，就是一个dp，
dp[i]为以i为结尾的方案数
转移就是
dp[i]=sigma{dp[j] | abs(a[i]-a[j])<=H}+1

复杂度为O(n^2) ,所以不可行,
然后观察了一下,由于转移的过程中正好是一个连续的和,所以想到前缀和优化,又因为是动态的 ,所以采用了树状数组优化.

在选取连续区间的时候我们用另一个数组来存储 ,然后排个序,去个重,用来二分查询位置.

二分的就是3个

  1. 是a[i]的位置 最后在这个位置+dp[i];
  2. 是a[i]+H 转移过程的右极限
  3. 是a[i] -H 转移过程的左极限

最后注意下代码细节 就可以了。
其实想到了如何DP这道题目就并不难了，奈何我个DP废。。。

附本题代码
-----------------------------------------------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
# include <bits/stdc++.h>

# define abs(x)          (((x)>0)?(x):-(x))
# define lalal           puts("*********")
# define Rep(a,b,c)      for(int a=(b);a<=(c);a++)
# define Req(a,b,c)      for(int a=(b);a>=(c);a--)
# define Rop(a,b,c)      for(int a=(b);a<(c);a++)
# define s1(a)           scanf("%d",&a)
typedef long long int LL;
using namespace std;
const int inf = 0x3f3f3f3f;
const int MOD = 9901;
/**************************************/
# define lowbit(x)  (x&-x)
const int N = 100000+5;
int sum[N],n,m;
int a[N],b[N],tot;
void update(int index,int val){
    for(int i=index;i<=tot;i+=lowbit(i))
        sum[i]+=val,sum[i]%=MOD;;
}
int getSum(int index){
    int ans = 0;
    for(int i=index;i>0;i-=lowbit(i))
        ans += sum[i],ans%=MOD;
    return ans ;
}

int BS(int val){
    int l=1,r=tot,mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(b[mid]==val) return mid;
        else if(b[mid]<val) l=mid+1;
        else r=mid-1;
    }
}
int lBS(int val){
    int l=1,r=tot,mid;
    int ans = 1;
    while(l<=r){
        mid=(l+r)>>1;
        if(b[mid] < val)
            l=mid+1;
        else ans=mid,r=mid-1;
    }
    return ans;
}
int rBS(int val){
    int l=1,r=tot,mid;
    int ans=tot;
    while(l<=r){
        mid=(l+r)>>1;
        if(b[mid] <= val) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}

int main(){
    while(~s1(n)){
        s1(m);
        Rep(i,1,n) s1(a[i]),b[i]=a[i];

        sort(b+1,b+n+1);
        tot=0;
        for(int i=1;i<=n;i++){
            if(i==1||b[i]!=b[i-1]){
                b[++tot]=b[i];
                sum[tot]=0;
            }
        }

        int id,l,r,val,ans=0;
        Rep(i,1,n){
            id=BS(a[i]);
            l=lBS(a[i]-m);
            r=rBS(a[i]+m);
            val=(getSum(r)-getSum(l-1)+MOD)%MOD;
            ans=(ans+val)%MOD;
            update(id,val+1);
        }

        printf("%d\n",ans);
    }
    return 0;
}