51nod1380 夹克老爷的逢三抽一

问题等价于选出$n / 3$个不相邻元素是权值和最大

这是一个经典贪心问题，同种树，拿堆维护即可，复杂度$O(n \log n)$

#include <queue>

#include <cstdio>

#include <cstring>

using namespace std;

extern inline char gc() {

    static char RR[], *S = RR + , *T = RR + ;

    if(S == T) fread(RR, , , stdin), S = RR;

    return *S ++;

}

inline int read() {

    int p = , w = ; char c = gc();

    while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }

    while(c >= '' && c <= '') p = p *  + c - '', c = gc();

    return p * w;

}

#define ll long long

#define ri register int

#define sid 200050

int n, k;

bool gg[sid];

ll ans, v[sid], pre[sid], nxt[sid];

struct Man {

    ll id, val;

    Man() {}

    Man(ll _i, ll _v) : id(_i), val(_v) {}

    friend bool operator < (Man a, Man b)

    { return a.val < b.val; }

} ;

priority_queue <Man> q;

inline void del(int o) {

    pre[nxt[o]] = pre[o];

    nxt[pre[o]] = nxt[o];

    gg[o] = ;

}

int main() {

    n = read();

    for(ri i = ; i <= n; i ++) v[i] = read();

    for(ri i = ; i <= n; i ++) {

        pre[i] = i - ; nxt[i] = i + ;

        q.push(Man(i, v[i]));

    }

    pre[] = n; nxt[n] = ;

    k = n / ;

    for(ri i = ; i <= k; i ++) {

        Man o; int id;

        while() {

            o = q.top(); q.pop();

            id = o.id; if(!gg[id]) break;

        }

        ans += v[id];

        v[id] = v[pre[id]] + v[nxt[id]] - v[id];

        q.push(Man(id, v[id]));

        del(pre[id]); del(nxt[id]);

    }

    printf("%lld\n", ans);

    return ;

}