[bzoj] 2151: 种树

发表于   |   分类于   |  

题意

　　n个点在一个环,选出k个点,使得点权和最大.点与点不能相邻.

传送门

分析

这道题基本上同”[bzoj] 1150: [CTSC2007]数据备份Backup”

代码

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
#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
int CH , NEG ;
template <typename TP>
inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>
inline void reads(TP& ret) {
truewhile (ret=getchar() , ret<'!') ;
truewhile (CH=getchar() , CH>'!') ;
}

#include <queue>

#define  maxn  200010LL

int a[maxn] ;

struct NODE {
trueint id ;
truebool operator < (const NODE& b) const { return a[id] < a[b.id] ; }
} ;


int n , k ;
std::priority_queue<NODE>h ;
int pre[maxn] , back[maxn] ;/*链表*/
bool del[maxn] = {0} ;

int main() {
int i , ans , pos , front , rear ;
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
trueread(n) , read(k) ;
trueif (k>(n/2)) { puts("Error!") ; goto END ; }
trueRep (i,1,n)
truetrueread(a[i]) ,
truetruepre[i] = i-1 , back[i] = i+1 ;
truepre[1] = n ; back[n] = 1 ;
trueRep (i,1,n)
truetrueh.push((NODE){i}) ;
trueans = 0 ;
truewhile (k --> 0) {
truetruewhile (del[h.top().id]) h.pop() ;
truetruepos = h.top().id , h.pop() ;
truetrueans += a[pos] ;
truetruefront = pre[pos] ;
truetruerear = back[pos] ;
truetruedel[front] = true ;
truetruedel[rear] = true ;
truetruepre[pos] = pre[front] ;
truetrueback[pos] = back[rear] ;
truetrueback[pre[pos]] = pos ;
truetruepre[back[pos]] = pos ;
truetruea[pos] = a[front]+a[rear]-a[pos] ;
truetrueh.push((NODE){pos}) ;
true}
trueprintf("%d\n", ans) ;
trueEND : ;
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章