容易想到需要把未使用的餐巾和已经使用的餐巾分开。
设$X_i$表示第$i$天已经的使用餐巾的点，设$Y_i$表示第$i$天还未使用的餐巾的点
我们知道使用过的餐巾数量 = 洗出来的餐巾数量 + 购买的餐巾数量（一个餐巾被多次洗出来算多次）。
右边是啥，我们不清楚，但是我们清楚每一天新增的使用过的餐巾的数量，所以源点向$X_i$连一条容量为$r_i$，费用为0的边。
接下来还有几种连边：
- $X_i$向$X_{i + 1}$连一条容量为$\infty$，费用为0的边（使用过的餐巾还是使用过的，$i < n$）。
- $Y_i$向$Y_{i + 1}$连一条容量为$\infty$，费用为0的边
- $X_i$向$Y_{i + M}$连一条容量为$\infty$，费用为$F$的边
- $X_i$向$Y_{i + N}$连一条容量为$\infty$，费用为$S$的边
对于第$i$天会用掉$r_i$的餐巾，所以$Y_i$向汇点连一条容量为$r_i$，费用为0的边。
还有一个购买餐巾，它直接会变成这一天的未使用过的餐巾，所以原点向$Y_i$连一条容量为$\infty$，费用为$p$的边。
Code
/**
* loj
* Problem#6008
* Accepted
* Time: 701ms
* Memory: 636k
*/
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
using namespace std;
typedef bool boolean; template <typename T>
void pfill(T* pst, const T* ped, T val) {
for ( ; pst != ped; *(pst++) = val);
} typedef class Edge {
public:
int ed, nx, r, c; Edge(int ed = , int nx = , int r = , int c = ) : ed(ed), nx(nx), r(r), c(c) { }
} Edge; typedef class MapManager {
public:
int* h;
vector<Edge> es; MapManager() { }
MapManager(int n) {
h = new int[(n + )];
pfill(h, h + n + , -);
} void addEdge(int u, int v, int r, int c) {
es.push_back(Edge(v, h[u], r, c));
h[u] = (signed) es.size() - ;
} void addArc(int u, int v, int cap, int c) {
addEdge(u, v, cap, c);
addEdge(v, u, , -c);
} Edge& operator [] (int p) {
return es[p];
}
} MapManager; const signed int inf = (signed) (~0u >> ); class Graph {
public:
int S, T;
MapManager g; int *le;
int *f, *mf;
boolean *vis; // be sure T is the last node
void set(int S, int T) {
this->S = S;
this->T = T;
f = new int[(T + )];
le = new int[(T + )];
mf = new int[(T + )];
vis = new boolean[(T + )];
pfill(vis, vis + T, false);
} int spfa() {
queue<int> que;
pfill(f, f + T + , inf);
que.push(S);
f[S] = , le[S] = -, mf[S] = inf;
while (!que.empty()) {
int e = que.front();
que.pop();
vis[e] = false;
for (int i = g.h[e], eu, w; ~i; i = g[i].nx) {
if (!g[i].r)
continue;
eu = g[i].ed, w = f[e] + g[i].c;
if (w < f[eu]) {
f[eu] = w, le[eu] = i, mf[eu] = min(mf[e], g[i].r);
if (!vis[eu]) {
vis[eu] = true;
que.push(eu);
}
}
}
}
if (f[T] == inf)
return inf;
int rt = ;
for (int p = T, e; ~le[p]; p = g[e ^ ].ed) {
e = le[p];
g[e].r -= mf[T];
g[e ^ ].r += mf[T];
rt += mf[T] * g[e].c;
}
return rt;
} int min_cost() {
int rt = , delta;
while ((delta = spfa()) != inf) {
rt += delta;
// cerr << delta << '\n';
}
return rt;
}
} Graph; int n;
int P, M, F, N, S;
int *require;
MapManager &g = Graph.g; inline void init() {
scanf("%d", &n);
scanf("%d%d%d%d%d", &P, &M, &F, &N, &S);
require = new int[(n + )];
g = MapManager(n << | );
for (int i = ; i <= n; i++) {
scanf("%d", require + i);
}
} inline void solve() {
int T = n << | ;
Graph.set(, T);
for (int i = ; i <= n; i++) {
g.addArc(, i, require[i], );
g.addArc(, i + n, inf, P);
if (i < n) {
g.addArc(i, i + , inf, );
g.addArc(i + n, i + n + , inf, );
}
if (i + M <= n)
g.addArc(i, i + n + M, inf, F);
if (i + N <= n)
g.addArc(i, i + n + N, inf, S);
g.addArc(i + n, T, require[i], );
}
printf("%d\n", Graph.min_cost());
} int main() {
init();
solve();
return ;
}