首页 题解

# 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 的边，表示购买干净的餐巾。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#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;
}