我们可以像下面这样建图
下面是对图的解释
- 把每天拆成两个点\(x_i\)(图中蓝色正方形)和\(Y_i\)（图中红色圆形）分别表示第i天要用的毛巾和用过的毛巾。
- 源点\(S\)到所有\(x_i\)连一条容量为该天需用毛巾数，费用为f的边，表示新买毛巾。（橙色边）
- 所有\(x_i\)到汇点\(T\)连一条容量为该天需用毛巾数，费用为0的边，表示每天都必须用足够的毛巾。（紫色边）
- 然后每天会产生若干用过的毛巾，所以再从\(S\)向所有的\(y_i\) 连边，容量同样是该天需用毛巾数，费用为0。（青色边）
- 这样，对某天用完后的毛巾进行消毒就对应了\(y\)到\(x\)的边：
- A方式 ：从每个\(Y_i\)到\(x_{i+a+1}\)连边，容量为无穷，费用为
fA（蓝色边） - B方式 ：从每个\(Y_i\)到\(x_{i+b+1}\)连边，容量为无穷，费用为
fB（绿色边） - 然后每天用过的毛巾可以拖延到下一天再送去消毒，所以每个\(y_i\)向\(Y_{i+1}\)连边，容量为无穷，费用为0。（红色边）
最后求最小费用最大流即可
AC-Code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN=2010,MAXM=100005;
//--Graph
const int S=2004,T=2005,INF=99999999;
struct Edge{int t,v,c,op,next;}E[MAXM];
int pFirst[MAXN],totE;
int Dis[MAXN],Pre[MAXN],NEd[MAXN];
bool inQ[MAXN];
//--Problem
int n,a,b,f,fA,fB;
void AddEdge(int s,int t,int v,int c)
{
int E1=++totE,E2=++totE;
E[E1].t=t;E[E1].v=v;E[E1].c= c;E[E1].op=E2;E[E1].next=pFirst[s];
pFirst[s]=E1;
E[E2].t=s;E[E2].v=0;E[E2].c=-c;E[E2].op=E1;E[E2].next=pFirst[t];
pFirst[t]=E2;
}
inline int X(int i)
{
return i*2-1;
}
inline int Y(int i)
{
return i*2;
}
bool Spfa()
{
memset(Dis,0x3f,sizeof(Dis));
memset(Pre,-1,sizeof(Pre));
memset(NEd,-1,sizeof(NEd));
memset(inQ,0,sizeof(inQ));
queue <int> Q;
Q.push(S);
Dis[S]=0;
int u,v;
while (!Q.empty())
{
u=Q.front();Q.pop();
inQ[u]=false;
for (int p=pFirst[u];p;p=E[p].next)
{
v=E[p].t;
if (E[p].v>0)
if (Dis[v]>Dis[u]+E[p].c)
{
Dis[v]=Dis[u]+E[p].c;
Pre[v]=u;NEd[v]=p;
if (!inQ[v])
{
inQ[v]=true;
Q.push(v);
}
}
}
}
return (Pre[T]!=-1);
}
int MinCostMaxFlow()
{
int u;
int Cost=0,tmpflow;
while (Spfa())
{
tmpflow=INF;
for (u=T;Pre[u]!=-1;u=Pre[u])
tmpflow=min(tmpflow,E[NEd[u]].v);
for (u=T;Pre[u]!=-1;u=Pre[u])
{
E[NEd[u]].v-=tmpflow;
E[E[NEd[u]].op].v+=tmpflow;
Cost+=tmpflow*E[NEd[u]].c;
}
}
return Cost;
}
int main()
{
int tmp;
scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fA,&fB);
for (int i=1;i<=n;i++)
{
scanf("%d",&tmp);
AddEdge(S,X(i),tmp,f);
AddEdge(X(i),T,tmp,0);
AddEdge(S,Y(i),tmp,0);
if (i<n)
AddEdge(Y(i),Y(i+1),INF,0);
if (i+a+1<=n)
AddEdge(Y(i),X(i+a+1),INF,fA);
if (i+b+1<=n)
AddEdge(Y(i),X(i+b+1),INF,fB);
}
printf("%d\n",MinCostMaxFlow());
return 0;
}