标题效果：给定一个长度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;
}版权声明：本文博主原创文章，博客，未经同意不得转载。