2288: 【POJ Challenge】生日礼物 - #include <Seter> - using namespace Orz;
2288: 【POJ Challenge】生日礼物
http://www.zybbs.org/JudgeOnline/problem.php?id=2288
| RunID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 160293 | Seter | 2288 | Accepted | 2708 kb | 52 ms | C/Edit | 2006 B | 2011-10-11 18:42:05 |
改掉一个随机对拍几十组才出现的脑残错误以后直接R1了……居然build前没有初始化位置数组……郁了个闷！
这道题一看就让人想到DP……然后我想了N天DP还是想不出来
这题正解其实是贪心……首先同号的一段肯定是合并起来的……然后把正的全加起来，如果超过了段数，那么就要去掉一段正的，或者并上一段负的，使得减小的值最小。具体操作是：在最小堆中保存每一段的绝对值，然后取最小的那段和左右两段合并起来。
怎么合并呢？我想了半天后来发现我2了……由于取出来的那一段是最小的，所以左右两段的绝对值之和减去取出来那段的绝对值必定是正的，直接替换掉这三段就可以了。这样每次段数都减少1，直到小于等于M为止。
所以题解应该是维护一个堆+一个链表！SPLAY貌似也可以。好长的代码，泪奔！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #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;} |
By Seter
评论 (0)