Eva

Time Limit: 10 Sec  Memory Limit: 162 MB
Description

某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB，而买一块新毛巾的费用为f（新毛巾是已消毒的，当天可以使用）；而且f>fA>fB。公司经理正在规划在这n天中，每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然，公司经理希望费用最低。你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒，使公司在这项n天的软件开发中，提供毛巾服务的总费用最低。

Input

第1行为n,a,b,f,fA,fB. 第2行为n1，n2，……，nn. （注：1≤f,fA,fB≤60，1≤n≤1000）

Output

最少费用

Sample Input

4  1  2  3  2  1                      
8  2  1  6  

Sample Output

38

HINT

Source

/**************************************************************

    Problem: 1221

    User: ictsing

    Language: C++

    Result: Accepted

    Time:1680 ms

    Memory:1568 kb

****************************************************************/

 

//BZOJ1221 [HNOI2001] 软件开发

#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

const int inf = 1e9;

int s=0,t=2000+1;

const int mt = 2000+5;

int fr[12000+5],to[12000+5],nxt[12000+5],cap[12000+5],cost[12000+5],adj[mt],cur[mt];

bool inq[mt];

int dis[mt],lev[mt];

int ecnt=1;

int qwq[mt];

int ans=0;

queue<int>q;

int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

void adde(int u,int v,int cc,int ccc)

{

    ecnt++,fr[ecnt]=u,to[ecnt]=v,nxt[ecnt]=adj[u],cap[ecnt]=cc,cost[ecnt]=ccc,adj[u]=ecnt;

    ecnt++,fr[ecnt]=v,to[ecnt]=u,nxt[ecnt]=adj[v],cap[ecnt]=0,cost[ecnt]=-ccc,adj[v]=ecnt;

}

bool spfa()

{

    while(!q.empty()) q.pop();

    for(int i=s;i<=t;i++) dis[i]=inf,inq[i]=0;

    q.push(s),dis[s]=0,inq[s]=1;

    while(!q.empty())

    {

        int u=q.front();q.pop();inq[u]=0;

        for(int i=adj[u];i;i=nxt[i])

        {

            int v=to[i];

            if(dis[v]>dis[u]+cost[i]&&cap[i])

            {

                dis[v]=dis[u]+cost[i];cur[v]=i;

                if(!inq[v]) inq[v]=1,q.push(v); 

            }

        }

    }

    return dis[t]!=inf;

}

void mcf()

{

    while(spfa())

    {

        int tmp=inf;

        for(int i=cur[t];i;i=cur[fr[i]]) tmp=min(tmp,cap[i]);

        ans+=dis[t]*tmp;

        for(int i=cur[t];i;i=cur[fr[i]]) cap[i]-=tmp,cap[i^1]+=tmp;

    } 

}

int main()

{

    int n=read(),a=read(),b=read(),f=read(),fa=read(),fb=read();

    for(int i=1;i<=n;i++)

        qwq[i]=read();

    for(int i=1;i<n;i++)

        adde(i,i+1,inf,0);

    for(int i=1;i<=n;i++)

        adde(s,i,qwq[i],0),adde(s,i+1000,inf,f);

    for(int i=1;i<=n;i++)

        adde(i+1000,t,qwq[i],0);

    for(int i=1;i+a+1<=n;i++)

        adde(i,i+1000+a+1,inf,fa);

    for(int i=1;i+b+1<=n;i++)

        adde(i,i+1000+b+1,inf,fb);

    mcf();

    printf("%d\n",ans);

    return 0;

}