http://www.zybbs.org/JudgeOnline/problem.php?id=2288

改掉一个随机对拍几十组才出现的脑残错误以后直接R1了……居然build前没有初始化位置数组……郁了个闷！

这道题一看就让人想到DP……然后我想了N天DP还是想不出来

这题正解其实是贪心……首先同号的一段肯定是合并起来的……然后把正的全加起来，如果超过了段数，那么就要去掉一段正的，或者并上一段负的，使得减小的值最小。具体操作是：在最小堆中保存每一段的绝对值，然后取最小的那段和左右两段合并起来。

怎么合并呢？我想了半天后来发现我2了……由于取出来的那一段是最小的，所以左右两段的绝对值之和减去取出来那段的绝对值必定是正的，直接替换掉这三段就可以了。这样每次段数都减少1，直到小于等于M为止。

所以题解应该是维护一个堆+一个链表！SPLAY貌似也可以。好长的代码，泪奔！

#include <stdio.h>
#define maxn 100002
#define Type struct link*
#define cmp(x,y) ((x)->v>(y)->v)
struct link{struct link *pr,*nx;int v,p;}*head,st[maxn],*stp=st;
typedef struct _Heap{Type Value[maxn];int Size;}Heap,*PHeap;
inline Swim(PHeap heap,int x){
	Type t;
	for(t=heap->Value[x];x&&cmp(heap->Value[x-1>>1],t);x=x-1>>1)(heap->Value[x]=heap->Value[x-1>>1])->p=x;
	return (heap->Value[x]=t)->p=x;
}inline Sink(PHeap heap,int x){
	Type t;int c;
	for(t=heap->Value[x];(x<<1^1)<heap->Size;x=c){
		c=(x<<1)+2==heap->Size?x<<1^1:cmp(heap->Value[x<<1^1],heap->Value[(x<<1)+2])?(x<<1)+2:x<<1^1;
		if(cmp(heap->Value[c],t))break;
		heap->Value[heap->Value[c]->p=x]=heap->Value[c];
	}return (heap->Value[x]=t)->p=x;
}inline Update(PHeap heap,int i,Type x){
	int flag=cmp(heap->Value[i],x);
	heap->Value[i]=x;
	return flag?Swim(heap,i):Sink(heap,i);
}inline getint(){
	int re=0,ch=getchar(),k;
	while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1;
	for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return k?-re:re;
}Heap h;int m,ans,c=1000000001,a;_Bool v;
main(){
	int i=0,n=getint()+2;
	if(!(m=getint()))return puts("0"),0;
	while(n--)if(a=n?n==1?-1000000001:getint():1,!v){
		if(a<=0)c-=a;
		else{
			if(head)(head->nx=stp)->pr=head;(head=h.Value[stp->p=h.Size++]=stp++)->v=c;
			c=a;v=1;
		}
	}else if(a>=0)c+=a;
	else{
		(head->nx=stp)->pr=head;ans+=(head=h.Value[stp->p=h.Size++]=stp++)->v=c;
		c=-a;v=0;m--;
	}for(i=h.Size>>1;i--;Sink(&h,i));
	while(m++<0){
		ans-=(head=h.Value[0])->v;
		if((n=head->nx->p)!=--h.Size)Update(&h,n,h.Value[h.Size]);
		if((n=head->pr->p)!=--h.Size)Update(&h,n,h.Value[h.Size]);
		head->v=head->nx->v+head->pr->v-head->v;Sink(&h,0);
		if(head->nx=head->nx->nx)head->nx->pr=head;
		if(head->pr=head->pr->pr)head->pr->nx=head;
	}printf("%d\n",ans);
	return 0;
}

• inline
• block