【问题描述】

 

 一个餐厅在相继的N天里，第i天需要Ri块餐巾(i=l，2，…，N)。餐厅可以从三种途径获得餐巾。

    (1)购买新的餐巾，每块需p分；

    (2)把用过的餐巾送到快洗部，洗一块需m天，费用需f分(f<p)。如m=l时，第一天送到快洗部的餐巾第二天就可以使用了，送慢洗的情况也如此。

    (3)把餐巾送到慢洗部，洗一块需n天(n>m)，费用需s分(s<f)。

    在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使N天总的费用最小。

 

 

【输入】

输入文件共 3 行，第 1 行为总天数；第 2 行为每天所需的餐巾块数；第 3 行为每块餐巾的新购费用 p ，快洗所需天数 m ，快洗所需费用 f ，慢洗所需天数 n ，慢洗所需费用 s 。

【输出】

一行，最小的费用

【样例】

napkin.in

3 

3 2 4 

10 1 6 2 3

napkin.out

64

【数据规模】

n<=200,Ri<=50

/*  这个题很神奇的是把一个点拆成旧餐巾和新餐巾（不知道那些dalao怎么想出来的）。  然后建模跑最小费用最大流：   由S向Xi连一条容量为ri，费用为0的边，代表每天会产生ri块旧餐巾；  由Yi向T连一条容量为ri，费用为0的边，代表每天需要ri块新餐巾（此边一定要填满）；  由Xi向Xi+1连一条容量为inf，费用为0的边，代表这些旧餐巾留到下一天处理；  由Xi到Yi+m(Xi+m<=day)连一条容量为inf，费用为f的边，代表快洗；  由Xi到Yi+n(Xi+n<=day)连一条容量为inf，费用为s的边，代表慢洗；  由S到Yi连一条容量为inf，费用为p的边，代表买新的。  PS：更新奇的是这样跑可以保证由Yi向T的边一定会填满。 */#include
     
      #include
      
       #define N 410#define M 100010#define inf 1000000000using namespace std;int head[N],dis[N],r[N],q[N*10],inq[N],fa[N],day,p,m,f,n,s,cnt=1,S,T,ans;struct node{    int u,v,pre,f,w;};node e[M];void add(int u,int v,int f,int w){    e[++cnt].u=u;e[cnt].v=v;e[cnt].f=f;e[cnt].w=w;e[cnt].pre=head[u];head[u]=cnt;    e[++cnt].u=v;e[cnt].v=u;e[cnt].f=0;e[cnt].w=-w;e[cnt].pre=head[v];head[v]=cnt;}bool spfa(){    for(int i=1;i<=T;i++)dis[i]=inf;    int h=0,t=1;dis[S]=0;q[1]=S;inq[S]=1;    while(h
       
        dis[now]+e[i].w){                dis[v]=dis[now]+e[i].w;                fa[v]=i;                if(!inq[v]){                    inq[v]=1;                    q[++t]=v;                }            }        }    }    return dis[T]!=inf;}void up_data(){    int i=fa[T],x=inf;    while(i!=S){        x=min(x,e[i].f);        i=fa[e[i].u];    }    i=fa[T];    while(i!=S){        e[i].f-=x;        e[i^1].f+=x;        ans+=x*e[i].w;        i=fa[e[i].u];    }}int main(){    freopen("napkin.in","r",stdin);    freopen("napkin.out","w",stdout);    scanf("%d",&day);    for(int i=1;i<=day;i++)scanf("%d",&r[i]);    scanf("%d%d%d%d%d",&p,&m,&f,&n,&s);    S=0;T=2*day+1;    for(int i=1;i<=day;i++){        add(S,i,r[i],0);        add(i+day,T,r[i],0);        if(i+1<=day)add(i,i+1,inf,0);        if(i+m<=day)add(i,i+m+day,inf,f);        if(i+n<=day)add(i,i+n+day,inf,s);        add(S,i+day,inf,p);    }    while(spfa())up_data();    printf("%d",ans);    return 0;}