网络流与线性规划24题中的餐巾计划吧
明显要拆点吧，把每一天拆成2个点，i，i+n起点 终点 容量 费用 s i inf c 每天都可以购买新毛巾 i t ni 0 每天的需求 s i+n ni 0 每天可能被洗的餐巾i+n i+n+1 inf 0 当前所有待洗的餐巾都可以等到下一天在洗（某种意义上相当于提前洗好了存起来）i+n i+a+1 inf ca 快速清洗a天后可用（注意这里使用的那天不洗，所以是第i+a+1天可以投入使用）i+n i+b+1 inf cb 同理
1 const inf=100000007; 2 type node=record 3 next,point,flow,cost:longint; 4 end; 5 6 var edge:array[0..2001000] of node; 7 pre,p,d,cur:array[0..2010] of longint; 8 q:array[0..2001000] of longint; 9 v:array[0..2010] of boolean; 10 x,ans,len,fm,sm,fw,sw,c,n,i,w,t:longint; 11 12 function min(a,b:longint):longint; 13 begin 14 if a>b then exit(b) else exit(a); 15 end; 16 17 procedure add(x,y,f,w:longint); 18 begin 19 inc(len); 20 edge[len].point:=y; 21 edge[len].flow:=f; 22 edge[len].cost:=w; 23 edge[len].next:=p[x]; 24 p[x]:=len; 25 end; 26 27 function spfa:boolean; 28 var f,r,i,x,y:longint; 29 begin 30 f:=1; 31 r:=1; 32 q[1]:=0; 33 fillchar(v,sizeof(v),false); 34 v[0]:=true; 35 for i:=1 to t do 36 d[i]:=inf; 37 d[0]:=0; 38 while f<=r do 39 begin 40 x:=q[f]; 41 v[x]:=false; 42 i:=p[x]; 43 while i<>-1 do 44 begin 45 y:=edge[i].point; 46 if edge[i].flow>0 then 47 if d[y]>d[x]+edge[i].cost then 48 begin 49 d[y]:=d[x]+edge[i].cost; 50 cur[y]:=i; 51 pre[y]:=x; 52 if not v[y] then 53 begin 54 v[y]:=true; 55 inc(r); 56 q[r]:=y; 57 end; 58 end; 59 i:=edge[i].next; 60 end; 61 inc(f); 62 end; 63 if d[t]=inf then exit(false) else exit(true); 64 end; 65 66 procedure mincost; 67 var neck,i,j:longint; 68 begin 69 while spfa do 70 begin 71 i:=t; 72 neck:=inf; 73 while i<>0 do 74 begin 75 j:=cur[i]; 76 neck:=min(edge[j].flow,neck); 77 i:=pre[i]; 78 end; 79 i:=t; 80 while i<>0 do 81 begin 82 j:=cur[i]; 83 dec(edge[j].flow,neck); 84 inc(edge[j xor 1].flow,neck); 85 i:=pre[i]; 86 end; 87 ans:=ans+neck*d[t]; 88 end; 89 end; 90 91 begin 92 readln(n,fm,sm,c,fw,sw); 93 len:=-1; 94 fillchar(p,sizeof(p),255); 95 t:=2*n+1; 96 for i:=1 to n do 97 begin 98 read(x); 99 add(i,t,x,0);100 add(t,i,0,0);101 add(0,i,inf,c);102 add(i,0,0,-c);103 add(0,i+n,x,0);104 add(n+i,0,0,0);105 end;106 for i:=1 to n do107 begin108 w:=i+fm+1;109 if w<=n then110 begin111 add(i+n,w,inf,fw);112 add(w,i+n,0,-fw);113 end;114 w:=i+sm+1;115 if w<=n then116 begin117 add(i+n,w,inf,sw);118 add(w,i+n,0,-sw);119 end;120 if i+1<=n then121 begin122 add(i+n,i+n+1,inf,0);123 add(i+n+1,i+n,0,0);124 end;125 end;126 mincost;127 writeln(ans);128 end.129 130