标题效果：给定一个长度n−1的序列，要求选出k个不相邻的数使得和最小

费用流显然能跑。并且显然过不去- -

考虑用堆模拟费用流

一个错误的贪心是每次取最小。这样显然过不去例子

我们把【每次取最小】改为【每次选择一个区间取反】。用堆来维护这些区间就可以

每次取出最小的区间，然后将两边合并

(比方如今堆里有[1,3][4,4][5,5])这三个区间，我取走了[4,4]并计入答案。那么我删除[1,3]和[5,5]这两个区间，并增加[1,5]这个区间，权值为[1,3]的权值+[5,5]的权值-[4,4]的权值

因为是费用流所以不用考虑边界问题 直接把[0,0]和[n+1,n+1]设为INF就可以

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define M 100100

using namespace std;

struct abcd{

    int x,val;

    abcd() {}

    abcd(int _,int __):

        x(_),val(__) {}

    bool operator < (const abcd &a) const

    {

        if( val != a.val )

            return val > a.val ;

        return x < a.x ;

    }

    bool operator == (const abcd &a) const

    {

        return x==a.x && val==a.val ;

    }

};

namespace Heap{

    priority_queue<abcd> heap,del_mark;

    void Insert(abcd x)

    {

        heap.push(x);

    }

    void Delete(abcd x)

    {

        del_mark.push(x);

    }

    void Pop()

    {

        while( del_mark.size() && heap.top()==del_mark.top() )

            heap.pop(),del_mark.pop();

        heap.pop();

    }

    abcd Top()

    {

        while( del_mark.size() && heap.top()==del_mark.top() )

            heap.pop(),del_mark.pop();

        return heap.top();

    }

}

int n,k,ans,a[M],val[M];

namespace Union_Find_Set{

    int fa[M],rank[M],l[M],r[M];

    int Find(int x)

    {

        if(!fa[x]||fa[x]==x)

            return fa[x]=x;

        return fa[x]=Find(fa[x]);

    }

    void Union(int x,int y)

    {

        int _l=l[x=Find(x)];

        int _r=r[y=Find(y)];

        if(rank[x]>rank[y])

            swap(x,y);

        if(rank[x]==rank[y])

            ++rank[y];

        fa[x]=y;

        l[y]=_l;r[y]=_r;

    }

}

int main()

{

    using namespace Union_Find_Set;

    int i;

    cin>>n>>k;

    for(i=1;i<=n;i++)

        scanf("%d",&a[i]);

    for(i=1;i<=n+1;i++)

        l[i]=i-1,r[i]=i+1;

    Heap::Insert(abcd(1,val[1]=0x3f3f3f3f));

    Heap::Insert(abcd(n+1,val[n+1]=0x3f3f3f3f));

    for(i=2;i<=n;i++)

        Heap::Insert(abcd(i,val[i]=a[i]-a[i-1]));

    for(i=1;i<=k;i++)

    {

        abcd temp=Heap::Top();Heap::Pop();

        ans+=temp.val;

        int _l=Find(l[temp.x]),_r=Find(r[temp.x]);

        Heap::Delete(abcd(_l,val[_l]));

        Heap::Delete(abcd(_r,val[_r]));

        temp.val=val[_l]+val[_r]-val[temp.x];

        Union(_l,temp.x);

        Union(temp.x,_r);

        temp.x=Find(temp.x);

        Heap::Insert(temp);

        val[temp.x]=temp.val;

    }

    cout<<ans<<endl;

    return 0;

}

版权声明：本文博主原创文章，博客，未经同意不得转载。