会T+M的方法一：
读完题很容易想到直接DP
\(f[i][j][k]\)表示到第\(i\)棵树为止共种了\(j\)棵树（\(k\)为1表示包括第\(i\)棵树，否则不包括）最大权值和为多少
显然，先不说会T，我们甚至开不下这么大的数组
优化掉一维，\(f[i][j]\)表示选\(i\)棵树，\(j\)表示是否选择，最大权值和为多少
这是一个不错的优化，但并不能改变你五十分的命运，显然还是会T
看脸的方法二：
既然会T，而且好像想不到还能够怎么优化了，那我们换一种做法
再怎么说，这道题也是放在提高试炼场——堆的最后一个嘛，我们考虑一下用堆来维护
遍历\(1 - n\)，用\(f[i]\)表示到i为止的权值和最大为多少，每次用堆顶来给\(f[i]\)赋值，\(f[i]=堆顶+a[i]\)，然后再把\(f[i-1]\)放入堆中
多好，复杂度nlgn，动规+堆优化，简直完美
可惜正确性受到了影响，几乎不可能拿分，因为有极大可能种的树的数量会超过k，这显然是不合法的
神奇的方法三：
那么好的两种方法都不行，这题太难了，不做了不做了
别着急啊，下面就要介绍一下神奇的贪心（正解）
我们会发现，如果我们取了一个点，那么它左右的就不能取了
我们将每个节点都放入堆里，然后每次取出最大的，答案加上它的权值，然后将原序列中它左右位置的节点定为不可取
这样贪心一定是对的吗？几乎是错的，但是这可不是一次性的贪心，这是有反悔机会的贪心
我们用双向链表来记录一下一个节点左右最近的可取节点
把前面定为不可取的改为把原序列中左右最近的可取节点定为不可取
当我们取出最大的节点后，答案加上它的权值，然后把权值改为\(a[l[i]]+a[r[i]]-a[i]\)，然后再放回堆中
什么意思呢？意思就是，如果我们在接下来又一次取出了它，也就说明取左右两侧的比取原节点更优，答案再加上它的权值，就相当于取了它左右两侧的节点，而且正好取两次，取两个节点，次数也对上了
最多取k次，也就保证了不超过k个节点，如果在取的过程中我们发现最大权值小于等于0了，那就弹出，因为再继续取已经无法产生正贡献了
下面放代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<queue>
#define ll long long
#define gc getchar
#define maxn 500005
using namespace std;
inline ll read(){
ll a=0;int f=0;char p=gc();
while(!isdigit(p)){f|=p=='-';p=gc();}
while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
return f?-a:a;
}int n,k,a[maxn],b[maxn],l[maxn],r[maxn];ll ans;
struct ahaha{
int id;ll v;
inline bool friend operator<(const ahaha x,const ahaha y){
return x.v<y.v;
}
};
priority_queue<ahaha>q;
int main(){
n=read();k=read();
for(int i=1;i<=n;++i){
a[i]=read();l[i]=i-1,r[i]=i+1;
q.push({i,a[i]});
}r[0]=1,l[n+1]=n;
while(k--){
while(b[q.top().id])q.pop();
ahaha z=q.top();q.pop();
if(z.v<=0)break;int i=z.id;
ans+=z.v;a[i]=a[l[i]]+a[r[i]]-a[i];
z.v=a[i];b[l[i]]=b[r[i]]=1;
l[i]=l[l[i]],r[i]=r[r[i]];
l[r[i]]=r[l[i]]=i;
q.push(z);
}
printf("%lld\n",ans);
return 0;
}
京公网安备 11010502036488号