【题目】http://www.oi.bbjy.com/n38c10.aspx
【算法分析】
O(nk)的dp。测得70分….
然后我YY到一个费用流，发现复杂度还是O(nk)，而且常数上必然比dp更慢。。。
于是翻看Sinya神牛的题解。。。Orz，原来是用贪心去做费用流。。。彻底膜拜。
http://sinyalee.com/blog/?p=427
拜一下先….
然后我YY到的费用流就和野牛的建图一样.
下面我就说一下我对那个贪心的理解.
首先我们想象我们是一只小蝌蚪,在流中寻找增广路….
(借一下野牛的图。。。)
然后可以YY到，我们找的增广路必然是从与S相连的一条未增广的边进去，然后向左或者向右若干次“上下波动”（当然也可以不上下动，直接进去T那里），然后跑到T点去。
如在a2->a3->a4这里波动。
我们如果增广路包含这一路径的话，就可以看成把a3给取消了，然后选择了a2和a4.
这样的话，连续的(不取，取，不取，取，不取….)就可以当成一个组。
注意最左边和最右边都必须为“不取”。
分成那个组以后，组的中间必然是不能做增广的，因为与S相连的边已经饱和~
所以就可以看成必须在两端搞进去。。。搞了以后，无论在左边开始搞还是右边开始搞，结果都是一样的，都是多了一个点，都是向两边迈进了一步。（画图YY一下即可）
然后就再把相邻的两组合并到一起。因为你和她已经弄成新的OXOXOXOXOXOXO….结构了
现在大体我们已经明了了，但是边沿情况怎么处理呢？
注意到，如果a1或者an已经选了，是不可能再取消的。那就别放进决策队列。
证明：
你YY一下费用流的增广过程，
会发现那里要么和S连的只属于一个点的边已经满流，要么和T连的只属于一个店的边已经满流，你是没有办法取消它了。。。
因为费用流是对的，所以这个是对的，因为这只是在模拟增广费用流。
然后综上一下，发现堆可以达到我们需要的每次找最短增广路径的目的。
增广增加的费用其实就是SUM[L[i],R[i]]-2*w[i]。
其中sum[i,j]表示a[i]到a[j]的和，w[i]表示这个区间已经选了的点的权值和。
根据这个做堆的关键字就可以了。
【其他】膜拜Sinya
【CODE】
#include
const int N=101111;
int n,K;
int a[N],inheap[N],fa[N],L[N],R[N];
int sum[N],ans;
inline int S(int i,int j){
if (!i) return sum[j];
return sum[j]-sum[i-1];
}
struct HeapType{
struct pt{int pos;int w;}h[N];
int tot;
bool cmp(int i,int j){
return (S(L[h[i].pos],R[h[i].pos])-h[i].w*2)
<(S(L[h[j].pos],R[h[j].pos])-h[j].w*2);
}
void swap(int i,int j){
int tmp;
tmp=h[i].pos; h[i].pos=h[j].pos; h[j].pos=tmp;
tmp=h[i].w; h[i].w=h[j].w; h[j].w=tmp;
inheap[h[i].pos]=i; inheap[h[j].pos]=j;
}
void up(int k){
while (k>1 && cmp(k,k/2)){
swap(k/2,k);
k/=2;
}
}
void down(int k){
int p;
while (k*2<=tot){
p=k*2;
if (p+1<=tot && cmp(p+1,p)) p++;
if (cmp(p,k)){
swap(p,k);
k=p;
}else break;
}
}
void ins(int pos,int w){
tot++;
h[tot].pos=pos;
h[tot].w=w;
inheap[pos]=tot;
up(tot);
}
void del(int inh){
if (!inh) return;
int tmp=h[inh].pos;
swap(tot,inh);
inheap[tmp]=0;
tot–;
up(inh);
down(inh);
}
}heap;
void input(){
cin >> n >> K;
int x;
for (int i=1;i<=n;i++){
scanf("%d",&x);
a[i]=x;
}
for (int i=1;i
sum[0]=0;
for (int i=1;i<=n+1;i++){
L[i]=i; R[i]=i; fa[i]=i;
sum[i]=sum[i-1]+a[i];
}
L[0]=0; R[0]=0; fa[0]=0;
heap.tot=0;
for (int i=1;i<=n;i++) heap.ins(i,0);
}
int gf(int k){
if (fa[k]==k) return k;
fa[k]=gf(fa[k]);
return fa[k];
}
void work(){
int i,k,ans=0,Lc,Rc,p,nw;
for (k=1;k<=K;k++){
p=gf(heap.h[1].pos);
ans+=S(L[p],R[p])-heap.h[1].w*2;
nw=S(L[p],R[p])-heap.h[1].w;
heap.del(1);
Lc=gf(L[p]-1);
nw+=heap.h[inheap[Lc]].w;
L[p]=L[Lc];
fa[Lc]=p;
heap.del(inheap[Lc]);
Rc=gf(R[p]+1);
nw+=heap.h[inheap[Rc]].w;
R[p]=R[Rc];
fa[Rc]=p;
heap.del(inheap[Rc]);
if (L[p]>0 && R[p]<=n) heap.ins(p,nw);
}
cout << ans << endl;
}
int main(){
freopen("backup.in","r",stdin);
freopen("backup.out","w",stdout);
input();
work();
return 0;
}
