jiry_2's Blog

把每天拆成两个，分别记为Xi，Yi，从S向Xi连一条流量为maxint，费用为f的边。从S向Yi连一条流量ni，费用为0的边。从Yi向Yi+1连一条流量maxint，费用为0的边（最开始做没连这个，直接连到X去，连了好多的边，所以一直TLE）。从Yi向Xi+a连一条流量为maxint，费用为fa的边。从Yi向Xi+b连一条流量为maxint，费用为fb的边。从Xi向T连一条流量为k，费用为0的边。这个网络的最小费用最大流的费用就是答案。

program p1221;
	const
		maxn=100000000;
	type
		bian=record
			next,f,w,point:longint;
		end;
	var
		p,d,after:array[0..5000] of longint;
		pd:array[0..5000] of boolean;
		x:array[1..400000] of longint;
		b:array[0..1500000] of bian;
		len,i,j,n,a,c,f,fa,fb,k:longint;
	function min(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	procedure ade(k1,k2,k3,k4:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].f:=k4;
			b[len].w:=k3;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3,k4:longint);
		begin
			ade(k1,k2,k3,k4);
			ade(k2,k1,-k3,0);
		end;
	function spfa:boolean;
		var
			head,i,j,now:longint;
		begin
			fillchar(x,sizeof(x),0);
			fillchar(pd,sizeof(pd),false);
			fillchar(d,sizeof(d),$3f);
			fillchar(after,sizeof(after),-1);
			x[1]:=0; head:=1; now:=0; pd[0]:=true; d[0]:=0;
			while head>now do begin
				inc(now);
				i:=p[x[now]];
				while i<>-1 do begin
					j:=b[i].point;{
					writeln(b[i].f,' ',b[i].w+d[x[now]],' ',d[j]);
					readln;}
					if (b[i].f>0) and (b[i].w+d[x[now]]<d[j]) then begin
						d[j]:=b[i].w+d[x[now]];
						after[j]:=i;
						if pd[j]=false then begin
							pd[j]:=true;
							inc(head);
							x[head]:=j;
						end;
					end;
					i:=b[i].next;
				end;
				pd[x[now]]:=false;
			end;{
			for i:=1 to n do
				write(d[i],' ');
			readln;}
			if after[n+1]>-1 then exit(true) else exit(false);
		end;
	function change:longint;
		var
			k,ans,tot,num,i,j:longint;
		begin
			i:=n+1; j:=after[i]; k:=maxn;
			while j<>-1 do begin
				k:=min(k,b[j].f);
				i:=b[j xor 1].point;
				j:=after[i];
			end;
			ans:=0; i:=n+1; j:=after[i];
			while j<>-1 do begin
				ans:=ans+k*b[j].w;
				dec(b[j].f,k);
				inc(b[j xor 1].f,k);
				i:=b[j xor 1].point;
				j:=after[i];
			end;{
			writeln(k,' ',ans);
		readln;	}
			exit(ans);
		end;
	function dinic:longint;
		var
			ans:longint;
		begin
			ans:=0;
			while spfa do
				ans:=ans+change;
			exit(ans);
		end;
	begin
		readln(n,a,c,f,fa,fb);
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		len:=-1;
		for i:=1 to n do
			add(0,i,f,maxn);
		for i:=1 to n-1 do
			add(n+i,n+i+1,0,maxn);
		for i:=1 to n-a-1 do
			add(n+i,i+a+1,fa,maxn);
		for i:=1 to n-c-1 do
			add(n+i,i+c+1,fb,maxn);
		for i:=1 to n do begin
			read(k);
			add(i,n*2+1,0,k);
			add(0,n+i,0,k);
		end;
		n:=n*2;
		writeln(dinic);
		{readln;
		readln;}
	end.