分析：首先看小范围的数据，很容易可以想到用DP，方程为f[i][j]=max(f[i-1][j],f[i-2][j-1]+a[i])，f[i][j]表示到第i个坑种了j棵树的最大收益。但是很显然不能过全部数据（亲测只有五十分）。正解以该要用优先队列，将所有的数据丢进一个大根堆中维护，然后每次取出一个最大的，然后把左右两边的坑合并，将其值变为a[l[i]]+a[r[i]]-a[i]再丢进堆中维护，因为容易证明，对于相邻的三个坑，要么选择a[i]，要么选择a[i-1]和a[i+1]两个。实在不理解就看代码吧。
Code：
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> #include<iomanip> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int N=5e5+7; ll n,m,a[N],l[N],r[N]; ll ans;bool vis[N]; struct Tree { ll val;int id; }t[N]; priority_queue<Tree>team; bool operator < (const Tree &a,const Tree &b) { return a.val<b.val; } inline ll read() { char ch=getchar();ll num=0;bool flag=false; while(ch<'0'||ch>'9'){if(ch=='-')flag=true;ch=getchar();} while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();} return flag?-num:num; } int main() { n=read();m=read(); for(int i=1;i<=n;i++) { a[i]=read(); t[i].id=i; t[i].val=a[i]; l[i]=i-1; r[i]=i+1; team.push(t[i]); } ll num=n; while(m--) { Tree x=team.top(); team.pop(); while(!team.empty()&&vis[x.id]) { x=team.top(); team.pop(); } if(x.val<0)break; ans+=x.val;num++; vis[x.id]=true; vis[l[x.id]]=true; vis[r[x.id]]=true; int ls=l[x.id],rs=r[x.id]; l[num]=l[ls];r[num]=r[rs]; r[l[num]]=num;l[r[num]]=num; a[num]=a[ls]+a[rs]-a[x.id]; team.push((Tree){a[num],num}); } printf("%lld",ans); return 0; }