【问题描述】

一个餐厅在相继的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 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<cstdio>
#include<iostream>
#define N 410
#define M 100010
#define inf 1000000000
using namespace std;
int head[N],dis[N],r[N],q[N*],inq[N],fa[N],day,p,m,f,n,s,cnt=,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=;e[cnt].w=-w;e[cnt].pre=head[v];head[v]=cnt;
}
bool spfa(){
for(int i=;i<=T;i++)dis[i]=inf;
int h=,t=;dis[S]=;q[]=S;inq[S]=;
while(h<t){
int now=q[++h];inq[now]=;
for(int i=head[now];i;i=e[i].pre){
int v=e[i].v;
if(e[i].f&&dis[v]>dis[now]+e[i].w){
dis[v]=dis[now]+e[i].w;
fa[v]=i;
if(!inq[v]){
inq[v]=;
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^].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=;i<=day;i++)scanf("%d",&r[i]);
scanf("%d%d%d%d%d",&p,&m,&f,&n,&s);
S=;T=*day+;
for(int i=;i<=day;i++){
add(S,i,r[i],);
add(i+day,T,r[i],);
if(i+<=day)add(i,i+,inf,);
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 ;
}
05-11 19:39