题解——种树（堆）

考试题目叫 so ，和这道种树几乎差不多

题面

Description

cyrcyr今天在种树，他在一条直线上挖了n个坑。这n个坑都可以种树，但为了保证每一棵树都有充足的养料，cyrcyr不会在相邻的两个坑中种树。而且由于cyrcyr的树种不够，他至多会种k棵树。假设cyrcyr有某种神能力，能预知自己在某个坑种树的获利会是多少（可能为负），请你帮助他计算出他的最大获利。

Input

第一行，两个正整数n,k。

第二行，n个正整数，第i个数表示在直线上从左往右数第i个坑种树的获利。

Output

输出1个数，表示cyrcyr种树的最大获利。

in.1
6 3
100 1 -1 100 1 -1

out.1
200

数据范围与约定

对于20%的数据，n<=20。

对于50%的数据，n<=6000。

对于100%的数据，n<=500000，k<=n/2,在一个地方种树获利的绝对值在1000000以内。

部分分做法

20分做法：

想怎样暴力，就怎样暴力。20分暴力做法之多。

50分做法：

DP，转移并不是特别难。
我们定义 dp[ i ][ j ][ 1/0 ] 表示递推到第 i 位，已经选了 j 个数, 1/0 表示当前位是否选择
实际上和没有上司的舞会的dp转移很像，不过是序列上的

dp[ i ][ j ][ 1 ] = dp[ i-1 ][ j-1 ][ 0 ]
dp[ i ][ j ][ 0 ] = max( dp[ i-1 ][ j ][ 0 ] , dp[ i-1 ][ j ][ 1 ] )

答案取 max{ dp[ N ][ K ][ 1/0 ] } ，滚掉第一位以节省空间

100% 数据思路

主要思路

1.处理选择矛盾的情况，即可以反悔。

我们考虑，当选择了一个当前最大值 a[ i ] 后，发现其实最优值要选择a[ i-1 ] 和 a[ i+1 ]，为了可以反悔，在选择下一个时，我们把 a[ i ]修改为 a[ i-1 ] + a[ i+1 ] - a[i] 。所以当 a[i] 被选后反悔时，我们在之后的选择中，我们就可以删去先前 a[ i ]的贡献而选择旁边两个。如果不反悔则不选，这样可以满足整个结构的最优性。

2.维护序列，不断满足上述条件

最大值我们考虑使用大根堆（优先队列来维护），先把所有值和编号压入堆，并且记录左右值的编号，在选择了 a[ i ]后进行上述操作，同时更行左右值得编号即可。整个操作进行K次，由于存在负值，所以要不断取最大值。

细节：
边界是不能合并越界，处理下即可。

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int MAXN = 500005  ;
inline int read(){
	int s=0,w=1 ; char g=getchar() ; while(g>'9'||g<'0'){ if( g=='-')w=-1;g=getchar() ;} 
	while(g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ; return s*w ;
}
priority_queue< pair<ll,int> >q ;
int N , K , tot ; 
ll ans = 0 , last = 0 ;
struct ap{
	int  l , r ; 
	ll val ;
	bool f ; 
}t[ MAXN ];
int main(){
	t[ 0 ].val = -10000000000000005LL ; //边界
	N = read() , K = read() ; tot = N ;
	for( int i = 1 ; i <= N ; ++i ){
		t[ i ].val = (ll)read() , t[ i ].l = i-1 , t[ i ].r = i+1 ;
		q.push( make_pair(t[ i ].val , i) ) ;
	}
	t[ N ].r = 0 ;//边界
	while( K-- ){
		int u = q.top().second ;
		if( t[ u ].f ){ K++;q.pop();continue; }
		ll v = q.top().first ; q.pop() ;
		ans += v ; t[ t[ u ].l ].f = t[ t[ u ].r ].f = true ;//更新答案
		t[ u ].val = t[ t[ u ].l ].val + t[ t[ u ].r ].val - t[ u ].val ; 
		t[ t[ t[ u ].l ].l ].r = u , t[ t[ t[ u ].r ].r ].l = u ;//updata，更新左右编号
		t[ u ].l = t[ t[ u ].l ].l , t[ u ].r = t[ t[ u ].r ].r ;
		q.push( make_pair( t[ u ].val , u ) ) ;
		last = max( last , ans ) ;
	}
	cout<<last ;
}