傳送門
線段樹經(jīng)典題目。

---

每次先找到最大子段和來更新答案，然后利用網(wǎng)絡流反悔退流的思想把這個最大字段乘-1之后放回去。
代碼：

#include<bits/stdc++.h> #define N 100005 #define lc (p<<1) #define rc (p<<1|1) #define mid (T[p].l+T[p].r>>1) using namespace std; inline int read(){int ans=0,w=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans*w; } int n,m,a[N],ans=0; struct node{int l,r,lmx,rmx,mmx,sum,lmn,rmn,mmn,lmxp,lmnp,rmxp,rmnp,mxl,mxr,mnl,mnr,tag;}T[N<<2]; inline int max(int a,int b){return a>b?a:b;} inline int min(int a,int b){return a<b?a:b;} inline node operator+(node a,node b){node ret;ret.sum=a.sum+b.sum,ret.l=a.l,ret.r=b.r;if(a.lmx>a.sum+b.lmx)ret.lmx=a.lmx,ret.lmxp=a.lmxp;else ret.lmx=a.sum+b.lmx,ret.lmxp=b.lmxp;if(a.lmn<a.sum+b.lmn)ret.lmn=a.lmn,ret.lmnp=a.lmnp;else ret.lmn=a.sum+b.lmn,ret.lmnp=b.lmnp;if(b.rmx>b.sum+a.rmx)ret.rmx=b.rmx,ret.rmxp=b.rmxp;else ret.rmx=b.sum+a.rmx,ret.rmxp=a.rmxp;if(b.rmn<b.sum+a.rmn)ret.rmn=b.rmn,ret.rmnp=b.rmnp;else ret.rmn=b.sum+a.rmn,ret.rmnp=a.rmnp;ret.mmx=a.mmx,ret.mxl=a.mxl,ret.mxr=a.mxr;if(a.rmx+b.lmx>ret.mmx)ret.mmx=a.rmx+b.lmx,ret.mxl=a.rmxp,ret.mxr=b.lmxp;if(b.mmx>ret.mmx)ret.mmx=b.mmx,ret.mxl=b.mxl,ret.mxr=b.mxr;ret.mmn=a.mmn,ret.mnl=a.mnl,ret.mnr=a.mnr;if(a.rmn+b.lmn<ret.mmn)ret.mmn=a.rmn+b.lmn,ret.mnl=a.rmnp,ret.mnr=b.lmnp;if(b.mmn<ret.mmn)ret.mmn=b.mmn,ret.mnl=b.mnl,ret.mnr=b.mnr;return ret; } inline void pushnow(int p){T[p].tag^=1,T[p].sum*=-1;T[p].lmx*=-1,T[p].rmx*=-1,T[p].lmn*=-1,T[p].rmn*=-1,T[p].mmx*=-1,T[p].mmn*=-1;swap(T[p].lmx,T[p].lmn),swap(T[p].rmx,T[p].rmn),swap(T[p].mmx,T[p].mmn);swap(T[p].lmxp,T[p].lmnp),swap(T[p].rmxp,T[p].rmnp);swap(T[p].mxl,T[p].mnl),swap(T[p].mxr,T[p].mnr); } inline void pushdown(int p){if(T[p].tag)T[p].tag^=1,pushnow(lc),pushnow(rc);} inline void build(int p,int l,int r){T[p].l=l,T[p].r=r,T[p].tag=0;if(l==r){T[p].sum=T[p].lmx=T[p].lmn=T[p].rmx=T[p].rmn=T[p].mmx=T[p].mmn=a[l];T[p].lmxp=T[p].rmxp=T[p].lmnp=T[p].rmnp=T[p].mxl=T[p].mxr=T[p].mnl=T[p].mnr=l;return;}build(lc,l,mid),build(rc,mid+1,r),T[p]=T[lc]+T[rc],T[p].tag=0; } inline void update(int p,int ql,int qr){if(T[p].l>qr||T[p].r<ql)return;if(ql<=T[p].l&&T[p].r<=qr)return pushnow(p);pushdown(p);if(qr<=mid)update(lc,ql,qr);else if(ql>mid)update(rc,ql,qr);else update(lc,ql,mid),update(rc,mid+1,qr);int tmp=T[p].tag;T[p]=T[lc]+T[rc],T[p].tag=tmp; } int main(){n=read(),m=read();for(int i=1;i<=n;++i)a[i]=read();build(1,1,n);for(int i=1;i<=m;++i){if(T[1].mmx<0){printf("%d",ans);return 0;}ans+=T[1].mmx,update(1,T[1].mxl,T[1].mxr);}printf("%d",ans);return 0; }

轉載于:https://www.cnblogs.com/ldxcaicai/p/9738173.html

總結

以上是生活随笔為你收集整理的2018.09.30 bzoj2288:生日礼物（贪心+线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。