首页 > 代码库 > bzoj 4842: [Neerc2016]Delight for a Cat
bzoj 4842: [Neerc2016]Delight for a Cat
Description
ls是一个特别堕落的小朋友，对于n个连续的小时，他将要么睡觉要么打隔膜，一个小时内他不能既睡觉也打隔膜
，因此一个小时内他只能选择睡觉或者打隔膜，当然他也必须选择睡觉或打隔膜，对于每一个小时，他选择睡觉或
打隔膜的愉悦值是不同的，对于第i个小时，睡觉的愉悦值为si，打隔膜的愉悦值为ei，同时又有一个奥妙重重的
规定：对于任意一段连续的k小时，ls必须至少有t1时间在睡觉，t2时间在打隔膜。那么ls想让他获得的愉悦值尽
量大，他该如何选择呢？
Input
第一行四个整数,n,k(1<=k<=n<=1000),t1,t2(0<=t1,t2<=k;t1+t2<=k),含义如上所述。
接下来一行n个整数，第i个整数si(0<=si<=1e9)表示睡觉的愉悦值。
接下来一行n个整数，第i个整数ei(0<=ei<=1e9)表示打隔膜的愉悦值。
Output
第一行输出最大的愉悦值。
接下来一行输出一个长度为n的字符串
第i个字符为E则代表第i小时在打隔膜，第i个字符为S则代表第i个小时在睡觉。
将每个点和每个长度D的区间看作边，限制条件看作流量上下界，差分建图，无源汇最大费用费用流
#include<cstdio>#include<queue>typedef long long i64;const int N=50007;const i64 inf=1ll<<60;int n,k,L,R,as[N],bs[N];int S,T,es[N],enx[N],ev[N],ec[N],e0[N],ep=2,pe[N];i64 l[N],ans=0;bool in[N];std::queue<int>q;void ae(int a,int b,int v,int c){ if(!v)return; es[ep]=b;enx[ep]=e0[a];ev[ep]=v;ec[ep]=c;e0[a]=ep++; es[ep]=a;enx[ep]=e0[b];ev[ep]=0;ec[ep]=-c;e0[b]=ep++;}void mins(int&a,int b){if(a>b)a=b;}bool sp(){ for(int i=1;i<=T;++i)l[i]=-inf; l[S]=0; q.push(S); while(q.size()){ int w=q.front();q.pop(); for(int i=e0[w];i;i=enx[i])if(ev[i]){ int u=es[i]; if(l[u]<l[w]+ec[i]){ l[u]=l[w]+ec[i]; pe[u]=i; if(!in[u])in[u]=1,q.push(u); } } in[w]=0; } if(l[T]>-inf){ int f=100000; for(int w=T,e;w!=S;w=es[e^1]){ e=pe[w]; mins(f,ev[e]); } for(int w=T,e;w!=S;w=es[e^1]){ e=pe[w]; ev[e]-=f; ev[e^1]+=f; } ans+=l[T]*f; return 1; } return 0;}int ee[N];int main(){ scanf("%d%d%d%d",&n,&k,&L,&R); R=k-R; for(int i=1;i<=n;++i)scanf("%d",as+i); for(int i=1;i<=n;++i)scanf("%d",bs+i); S=n-k+3;T=S+1; for(int i=1;i<=n-k+1;++i)ae(i,i+1,R-L,0); ae(1,T,L,0); ae(S,n-k+2,L,0); for(int i=1;i<=n;++i){ ans+=bs[i]; int x=i-k+1,y=i+1; if(x<1)x=1; mins(y,n-k+2); int c=as[i]-bs[i]; if(c<=0)ee[i]=ep,ae(y,x,1,c); else{ ae(y,T,1,0); ae(S,x,1,c); ee[i]=ep; ae(x,y,1,-c); } } while(sp()); printf("%lld\n",ans); for(int i=1;i<=n;++i){ int c=as[i]-bs[i]; putchar((c<=0)==(!ev[ee[i]])?‘S‘:‘E‘); } return 0;}
bzoj 4842: [Neerc2016]Delight for a Cat
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。