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