bzoj 2151 种树 题解

传送门

---

【分析】

反悔贪心

若没有相邻不可选的限制，则用优先队列维护前 (m) 大，然后直接求和即可

现考虑对贪心如何反悔：

假设我们处于开局，什么都没选的状态

当贪心选择第 (i) 个时，由于相邻不可选，需要删除 ((i-1)) 和 ((i+1)) 的权值，避免产生相邻的选择

但实际上有可能 (a_{i-1}+a_{i+1}>a_i) 从而反悔之前的贪心，故我们补回一个点，权值为 (a_{i-1}+a_{i+1}-a_i)

若后续过程中，我们选择了该点，则代表我们反悔了选择 (a_i) 的这次贪心；但同时，我们选择的点数仍然+1

此时，我们删除点 ((i-2)) 与 ((i+2)) 的权值，同样是为了避免产生相邻的选择

但与上面相同，实际上可能 (a_{i-2}+a_i+a_{i+2}>a_{i-1}+a_{i+1}>a_i) 从而反悔之前的贪心，故我们同样补回一个点，权值为 (a_{i-2}+a_i+a_{i+2}-a_{i-1}-a_{i+1}=a_{i-2}+a_{i+2}-(a_{i-1}-a_{i+1}-a_i))

而这次过程等价于将上一步新产生的补充点看成同样的一个点，再进行上一步的补充操作

---

因此我们不区分补充的点与原有的点，直接将原有的点塞进优先队列中，并维护一个循环链表

当我们从优先队列中取出一个未被打过标记的点时，将它与它前后，共三个点打上标记

之后，我们新建权值为 (a_{i-1}+a_{i+1}-a_i) 的点，并在循环队列中顶替原来的三个点即可

执行 (m) 次得到答案

---

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef double db;
#define fi first
#define se second
const int MAXN=4e5+10;
int n, m, a[MAXN], pre[MAXN], suf[MAXN], cntc;
bool used[MAXN];
priority_queue<pii> pq;
inline int maxc(){
    int val, pos;
    while(pq.size()){
        val=pq.top().fi;
        pos=pq.top().se;
        pq.pop();
        if(!used[pos])
            break;
    }
    if(used[pos]) return 0;

    used[pos]=used[ pre[pos] ]=used[ suf[pos] ]=1;
    a[++cntc]=a[ pre[pos] ]+a[ suf[pos] ]-a[pos];
    suf[ pre[pre[pos]] ]=cntc;
    pre[ suf[suf[pos]] ]=cntc;
    pre[cntc]=pre[pre[pos]];
    suf[cntc]=suf[suf[pos]];
    pq.push( pii(a[cntc], cntc) );
    return val;
}
inline void init(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        pre[i]=i-1;
        suf[i]=i+1;
        pq.push( pii(a[i], i) );
    }
    suf[n]=1; pre[1]=n;
    cntc=n;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    init();
    if(n<m+m){
        cout<<"Error!";
    }
    else{
        int res=0;
        for(int i=1;i<=m;++i)
            res+=maxc();
        cout<<res;
    }
    cout.flush();
    return 0;
}