这估计是网络流$24$题图最难建的一个了..刚了2h没刚出来
首先，肯定要把每一天拆成$2$个点，表示白天和晚上
正常的思路一般是：源点和白天连，白天和晚上连边，晚上和汇点连，晚上再分别向快洗慢洗对应的早上连边，白天和白天之间连边，然后跑费用流..
然而我们发现怎么跑都不行啊！为啥快洗慢洗的边都走不了了呢？？？
因为快洗慢洗会减少流量，不满足费用流：最小费用最大流的定义
所以我们要改一下建图方式，拆点的思路不变：
1.源点$s$向晚上连边，流量为$a_{i}$，费用为$0$，表示这一天晚上获得了$a_{i}$个旧餐巾
2.白天向汇点$t$连边，流量为$a_{i}$，费用为$0$，表示这一天白天需要$a_{i}$个新餐巾
3.第$i$天白天和向$i+1$白天连边，流量为$inf$，费用为$0$，表示今天白天的新餐巾可以留到明天白天
4.第$i$天晚上向第$i+$慢洗天数/$i+$快洗天数的白天连边，流量为$inf$，费用为慢洗费用/快洗费用，表示把旧餐巾送洗
5.源点$s$向白天连边，流量为$inf$，费用为p，表示白天还可以直接购买新餐巾
然后跑最小费用最大流即可
————————————————————分割线-————————————————————————————
2020.7.17 upd
发现自己以前写的题解有点问题，其实应该是旧点间和新旧点间都连，而不是新点间，但结果是一样的
此外，1是由于让新点向旧点连边是无用的，流直接从新点流向T了。
第i天必然消耗ri个新餐巾，产生ri个旧餐巾
所以S直接向旧点连流量为ri，费用为0的边，把同一天的新旧点彻底拆开
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define N1 4010 5 #define M1 25010 6 #define ll long long 7 #define dd double 8 #define inf 0x3f3f3f3f 9 using namespace std; 10 11 int gint() 12 { 13 int ret=0,fh=1;char c=getchar(); 14 while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();} 15 while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();} 16 return ret*fh; 17 } 18 struct Edge{ 19 int head[N1],to[M1<<1],nxt[M1<<1],flow[M1<<1],cost[M1<<1],cte; 20 void ae(int u,int v,int F,int C) 21 { 22 cte++; to[cte]=v; flow[cte]=F; cost[cte]=C; 23 nxt[cte]=head[u]; head[u]=cte; 24 } 25 }e,E; 26 int n,nn,S,T,p,A,B,C,D; 27 int a[N1],que[M1<<1],hd,tl,cost[N1],flow[N1],use[N1],id[N1],de; 28 int spfa() 29 { 30 int x,j,v; 31 memset(cost,0x3f,sizeof(cost)); memset(flow,0,sizeof(flow)); 32 hd=1,tl=0; que[++tl]=S; cost[S]=0; flow[S]=inf; use[S]=1; 33 while(hd<=tl) 34 { 35 x=que[hd++]; 36 for(j=e.head[x];j;j=e.nxt[j]) 37 { 38 v=e.to[j]; 39 if( cost[v]>cost[x]+e.cost[j] && e.flow[j]>0 ) 40 { 41 cost[v]=cost[x]+e.cost[j]; id[v]=j; 42 flow[v]=min(flow[x],e.flow[j]); 43 if(!use[v]) que[++tl]=v, use[v]=1; 44 } 45 } 46 use[x]=0; 47 } 48 de++; 49 return cost[T]!=inf; 50 } 51 ll EK() 52 { 53 int x,fl;ll tcost=0; 54 while(spfa()) 55 { 56 fl=flow[T]; tcost+=1ll*fl*cost[T]; 57 for(x=T;x!=S;x=e.to[id[x]^1]) 58 { 59 e.flow[id[x]]-=fl; 60 e.flow[id[x]^1]+=fl; 61 } 62 } 63 return tcost; 64 } 65 66 int main() 67 { 68 scanf("%d",&n); nn=2*n; 69 int i,j; S=0; T=nn+1; e.cte=1; 70 for(i=1;i<=n;i++) a[i]=gint(); 71 p=gint(); A=gint(); B=gint(); C=gint(); D=gint(); 72 for(i=1;i<=n;i++) e.ae(i+n,T,a[i],0), e.ae(T,i+n,0,0); 73 for(i=1;i<=n;i++) e.ae(S,i,a[i],0), e.ae(i,S,0,0); 74 for(i=1;i<=n;i++) e.ae(S,i+n,inf,p), e.ae(i+n,S,0,-p); 75 for(i=n+1;i<n+n;i++) e.ae(i,i+1,inf,0), e.ae(i+1,i,0,0); 76 for(i=1;i+A<=n;i++) e.ae(i,i+A+n,inf,B), e.ae(i+A+n,i,0,-B); 77 for(i=1;i+C<=n;i++) e.ae(i,i+C+n,inf,D), e.ae(i+C+n,i,0,-D); 78 printf("%lld ",EK()); 79 return 0; 80 }