首页 题解

# Description

Luogu 传送门

# Solution

明显是要使用费用流，考虑如何建图。

把每一天拆成晚上和早上两个点，每天晚上会获得脏餐巾，早上会获得干净的餐巾。

  • 从源点向每天晚上连流量为 xx，费用为 0 的边，表示晚上会获得当天所需的 xx 条脏餐巾。
  • 从每天早上向汇点连流量为 xx，费用为 0 的边，表示每天早上提供 xx 条干净的餐巾给汇点，如果满流则合法。
  • 从每天晚上向第二天的早上连流量为 inf\text{inf}，费用为 0 的边，表示把当天的脏餐巾留给第二天。
  • 快洗：第 ii 天晚上向第 i+t1i + t_1 天早上连流量为 inf\text{inf}，费用为 w1w_1 的边，表示从第 ii 天开始洗，第 i+t1i + t_1 天能收到餐巾。
  • 慢洗：同快洗。
  • 购买：从源点向每天早上连一条流量为 inf\text{inf}，费用为 mm 的边，表示购买干净的餐巾。

注意连边的时候判一下边界。

#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 4010;
const int inf = 1e9;
const int INF = 1e18;
int n, m, t1, w1, t2, w2, s, t;
int a[N];
struct node{
    int v, w, cost, nxt;
}edge[N * 15];
int head[N], tot = 1;
inline void add(int x, int y, int z, int c){
    edge[++tot] = (node){y, z, c, head[x]};
    head[x] = tot;
}
inline void Add(int x, int y, int z, int c){
    add(x, y, z, c), add(y, x, 0, -c);
}
int dis[N], ans;
bool vis[N];
inline bool spfa(){
    memset(vis, 0, sizeof(vis));
    memset(dis, 63, sizeof(dis));
    queue <int> q;
    q.push(s), dis[s] = 0;
    while(!q.empty()){
        int x = q.front(); q.pop();
        vis[x] = 0;
        for(int i = head[x]; i; i = edge[i].nxt){
            int y = edge[i].v;
            if(edge[i].w && dis[y] > dis[x] + edge[i].cost){
                dis[y] = dis[x] + edge[i].cost;
                if(!vis[y]) vis[y] = 1, q.push(y);
            }
        }
    }
    return dis[t] < INF;
}
inline int dfs(int x, int lim){
    if(x == t || !lim) return lim;
    int flow = 0; vis[x] = 1;
    for(int i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(!vis[y] && edge[i].w && dis[y] == dis[x] + edge[i].cost){
            int res = dfs(y, min(lim, edge[i].w));
            lim -= res, flow += res, edge[i].w -= res, edge[i ^ 1].w += res, ans += 1ll * res * edge[i].cost;
        }
    }
    return flow;
}
inline int solve(){
    while(spfa()) dfs(s, inf);
    return ans;
}
signed main(){
    // freopen("P1251.in", "r", stdin);
    // freopen("P1251.out", "w", stdout);
    n = read();
    s = 0, t = 2 * n + 1;
    for(int i = 1, x; i <= n; ++i)
        x = read(), Add(s, i, x, 0), Add(i + n, t, x, 0);
    m = read(), t1 = read(), w1 = read(), t2 = read(), w2 = read();
    for(int i = 1; i <= n; ++i){
        if(i + 1 <= n) Add(i, i + 1, inf, 0);
        if(i + t1 <= n) Add(i, i + n + t1, inf, w1);
        if(i + t2 <= n) Add(i, i + n + t2, inf, w2);
        Add(s, i + n, inf, m);
    }
    write(solve()), puts("");
    return 0;
}