您的位置: 首页  >  IT文章  >  BC.5200.Trees(dp) Trees

BC.5200.Trees(dp) Trees

分类: IT文章 • 2022-05-12 12:36:50
 
 Accepts: 156
 
 Submissions: 533
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
Problem Description

Today CodeFamer is going to cut trees.There are  are in the same block if and only if they are fitting in one of blow rules:

1)x+1=y or y+1=x;

2)there exists an uncutted tree which is numbered z.

Now CodeFamer want to cut some trees whose height is not larger than some value, after those trees are cut, how many tree blocks are there?

Input

Multi test cases (about 15).

For each case, first line contains two integers  queries.

In the following  which indicates the height of the trees.

In the following  which indicates CodeFamer’s queries.

Please process to the end of file.

[Technical Specification]

50000

)

)

Output

For each ].

Sample Input
3 2
5
2
3
6
2
Sample Output
0
2
Hint
In this test case, there are 3 trees whose heights are 5 2 3. For the query 6, if CodeFamer cuts the tree whose height is not large than 6, the height form of left trees are -1 -1 -1(-1 means this tree was cut). Thus there is 0 block. For the query 2, if CodeFamer cuts the tree whose height is not large than 2, the height form of left trees are 5 -1 3(-1 means this tree was cut). Thus there are 2 blocks.
 1 #include<stdio.h>
 2 #include<map>
 3 #include<algorithm>
 4 #include<set>
 5 #include<string.h>
 6 using namespace std;
 7 int n , m ;
 8 const int M = 50000 + 10 ;
 9 int cut[M] ;
10 bool vis[M] ;
11 pair <int , int> a[M] ;
12 
13 void solve ()
14 {
15     for (int i = 1 ; i <= n ; i++) {
16         scanf ("%d" , &a[i].first) ;
17         a[i].second = i ;
18     }
19     sort (a + 1 , a + n + 1) ;
20     for (int i = n ; i >= 1 ; i --) {
21         cut [i] = cut [i + 1] ;
22         int now = a[i].second ;
23         if (vis[now - 1] && vis[now + 1] ) {
24             cut[i] -- ;
25         }
26         else if (!vis[now - 1] && !vis[now + 1]) {
27             cut[i] ++ ;
28         }
29         vis[now] = 1 ;//1 代表没砍 ， 0 代表砍了
30     }
31     while (m--) {
32         int h ;
33         scanf ("%d" , &h) ;
34         int x = upper_bound (a + 1 , a + n + 1 , make_pair (h , n + 1) ) - a ;
35         if (x > n) puts ("0") ; else printf ("%d
" , cut[x]) ;
36     }
37 }
38 
39 int main ()
40 {
41    // freopen ("a.txt" , "r" , stdin ) ;
42     while (~ scanf ("%d%d" , &n , &m)) {
43         memset (vis , 0 , sizeof(vis)) ;
44         memset (cut , 0 , sizeof(cut)) ;
45         solve () ;
46     }
47     return 0 ;
48 }
View Code

假设0为砍掉状态 ， 1 为活着状态。

假设一排树的高度为               2 4 3 1 6 5

他们一开始都为                      0 0 0 0 0 0

若只有最高的活着，状态变为  0 0 0 0 1 0   sta[6] = 1

若有第2高的活着，状态为       0 0 0 0 1 1   sta[5] = sta[6] = 1 , 显而易见第5，6棵树构成block , 不用+ 1

若有第3高的活者，状态为       0 1 0 0 1 1   sta[4] = sta[5] + 1 = 2 , 因为第{2} ， {5 ， 6}都为block

若有第4高的活着，状态为       0 1 1 0 1 1   sta[3] = sta[4]  = 2 ; {2 ， 3} ， {5 ， 6}

如有第5高的活着，状态为       1 1 1 0 1 1　sta[2] = sta[3] = 2 ;  {1 , 2 , 3} , {5 , 6}

如果都活着， 状态为               1 1 1 1 1 1   sta[1] = sta[2] - 1 ; 只有{1 ， 2 ，3 ， 4 ， 5 ， 6} 一个block

虽然很orz，但过然是dp吧

相关推荐