题目描述
cyrcyr今天在种树，他在一条直线上挖了n个坑。这n个坑都可以种树，但为了保证每一棵树都有充足的养料，cyrcyr不会在相邻的两个坑中种树。而且由于cyrcyr的树种不够，他至多会种k棵树。假设cyrcyr有某种神能力，能预知自己在某个坑种树的获利会是多少（可能为负），请你帮助他计算出他的最大获利。
输入输出格式
输入格式：
第一行，两个正整数n,k。
第二行，n个正整数，第i个数表示在直线上从左往右数第i个坑种树的获利。
输出格式：
输出1个数，表示cyrcyr种树的最大获利。
输入输出样例
输入样例#1： 复制
6 3 100 1 -1 100 1 -1
输出样例#1： 复制
200
说明
对于20%的数据，n<=20。
对于50%的数据，n<=6000。
对于100%的数据，n<=500000，k<=n/2,在一个地方种树获利的绝对值在1000000以内。
因为这两天学弟们在讲关于贪心的题目，我也来总结几个贪心的题目吧，主要是可以后悔的贪心题目
这个题显然可以通过dp来写，但是复杂度要n^2，f[i][j]表示种到第i棵树且种了j棵的最大获利，则f[i][j]=max(f[i-1][j],f[i-2][j-1]+a[i])
所以我们考虑贪心，他要求如果取了一个位置，那么剩下来的两个位置就不能取了，考虑先取前k个，用个堆来维护，每次拿出来下标以后，就标记左右两边，我们考虑
1 5 20 19 -5
开始最大选择20，选择第三个后，2和4位置就不能选了，但是5 + 19 > 20，明显是更优的，那我们可以选择放弃以前选的20
就可以a[2] + a[4] - a[3]作为当前的价值，再次放进堆当中维护，如果堆中的值是<0的，那么显然对我们的答案也就没有贡献了，然后还需要用个l和r数组来维护左右边界，注意更新。
不懂可以再看看代码吧：
#include <bits/stdc++.h>
#include <time.h>
#define fi first
#define se secondusing namespace std;typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int> P;
const int maxn = 2e6 + 5000;
const ll mod = 1e9 + 7;
inline int sign(db a) { return a < -eps ? -1 : a > eps;}
inline int cmp(db a,db b){ return sign(a - b);}
ll mul(ll a,ll b,ll c) { ll res = 1; while(b) { if(b & 1) res *= a,res %= c; a *= a,a %= c,b >>= 1; } return res;}
ll phi(ll x) { ll res = x; for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = res / i * (i - 1); while(x % i == 0) x /= i; } if(x > 1) res = res / x * (x - 1); return res;}
int fa[maxn];
int Find(int x) { if(x != fa[x]) return fa[x] = Find(fa[x]); return fa[x];}
ll c,n,k;
ll a[maxn];
struct node{ll val;int id;bool operator < (const node & b) const{return val < b.val;}
}t[maxn];
priority_queue<node>q;
int l[maxn],r[maxn];
bool vis[maxn];
int main() {ios::sync_with_stdio(false);while(cin >> n >> k){for(int i = 1;i <= n;i++) cin >> t[i].val,t[i].id = i,a[i] = t[i].val;for(int i = 1;i <= n;i++){q.push(t[i]);l[i] = i - 1;r[i] = i + 1;}ll ans = 0;int num = n;for(int i = 1;i <= k;i++){node x = q.top();q.pop();while(!q.empty() && vis[x.id]) x = q.top(),q.pop();if(x.val < 0) break;ans += x.val,num++;vis[x.id] = 1,vis[l[x.id]] = 1,vis[r[x.id]] = 1;int ll = l[x.id],rr = r[x.id];l[num] = l[ll],r[num] = r[rr];r[l[num]] = num,l[r[num]] = num;a[num] = a[ll] + a[rr] - a[x.id];q.push(node{a[num],num});}cout << ans << endl;}cerr << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}