BZOJ 2151 种树（循环链表）

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2151

【题目大意】

　　在一个长度为n的数字环中挑选m个不相邻的数字使得其和最大

【题解】

　　我们用大根堆和循环链表维护数字的相邻关系和删去操作，
　　对于相邻点不能选取这个条件，我们在每次删去一个点之后，加入一个新的点
　　权值和为周围点减去删去的点，增加反向弧，这样子就可以通过之后的选取实现退流操作
　　保证答案最优。

【代码】

#include <cstdio>

#include <queue>

using namespace std;

const int N=200010;

namespace Circular_List{

    bool del[N];

    int n,nxt[N],pre[N],val[N];

    typedef pair<int,int> P;

    priority_queue<P,vector<P> > Q; // 大根堆

    void Initialize(){

        while(Q.size())Q.pop();

        for(int i=1;i<=n;i++)pre[i]=i-1; pre[1]=n;

        for(int i=1;i<=n;i++)nxt[i]=i+1; nxt[n]=1;

        for(int i=1;i<=n;i++)Q.push(make_pair(val[i],i)),del[i]=0;

    }

    void Del(int x){

       del[x]=1;

       nxt[pre[x]]=nxt[x];

       pre[nxt[x]]=pre[x];

       nxt[x]=pre[x]=0;

    }

    int Get(){

        while(del[Q.top().second])Q.pop();

        int res=Q.top().second; Q.pop();

        return res;

    }

}

int m;

int main(){

	using namespace Circular_List;

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)scanf("%d",&val[i]);

    if(m>n/2){puts("Error!");return 0;}

    Initialize();

    int ans=0;

    for(int i=1;i<=m;i++){

         int x=Get();

         ans+=val[x];

         val[x]=val[pre[x]]+val[nxt[x]]-val[x];

         Del(pre[x]); Del(nxt[x]);

         Q.push(make_pair(val[x],x));

    }printf("%d\n",ans);

    return 0;

}