Problem A. 摆花

多段最大子段和,设计 DP 解决即可。

时间复杂度 $\mathcal O(n)$

#include <bits/stdc++.h>

using namespace std;

template <typename T>
void read(T& x) {
    x = 0;
    int c = 0, f = 0;
    for (; !isdigit(c); c = getchar()) f |= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c & 15);
    x = f ? -x : x;
}

const int N = 1e6 + 5;

int n;
int a[N];
long long dp[N][5];
long long g[N][3];

int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]);
    memset(dp, ~0x3f, sizeof dp);
    memset(g, ~0x3f, sizeof g);
    dp[1][0] = g[1][0] = a[1];
    for (int i = 2; i <= n; i++) {
        dp[i][0] = max(dp[i - 1][0], 0ll) + a[i];
        dp[i][1] = g[i - 2][0] + a[i];
        dp[i][2] = max({dp[i - 1][2] + a[i], dp[i - 1][1] + a[i], dp[i][1]});
        dp[i][3] = g[i - 2][1] + a[i];
        dp[i][4] = max({dp[i - 1][4] + a[i], dp[i - 1][3] + a[i], dp[i][3]});
        g[i][0] = max(g[i - 1][0], dp[i][0]);
        g[i][1] = max(g[i - 1][1], dp[i][2]);
        g[i][2] = max(g[i - 1][2], dp[i][4]);
    }
    long long ans = ~0x3f3f3f3f3f3f3f3f;
    for (int i = 1; i <= n; i++) ans = max(ans, dp[i][4]);
    printf("%lld\n", ans);
    return 0;
}

Problem B. 多米诺骨牌

二分图最大匹配经典模型,可以用 Dinic 解决。

时间复杂度 $\mathcal O(n^2m)$

#include <bits/stdc++.h>

using namespace std;

template <typename T>
void read(T& x) {
    x = 0;
    int c = 0, f = 0;
    for (; !isdigit(c); c = getchar()) f |= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c & 15);
    x = f ? -x : x;
}

const int N = 100005, M = N * 10;

struct Dinic {
    int nxt[M], to[M], wt[M];
    int head[N], arc[N];
    int edge_cnt;

    Dinic() {
        edge_cnt = 1;
    }

    void add_edge(int u, int v, int w) {
        to[++edge_cnt] = v;
        wt[edge_cnt] = w;
        nxt[edge_cnt] = head[u];
        head[u] = edge_cnt;
    }

    void link(int u, int v, int w) {
        add_edge(u, v, w);
        add_edge(v, u, 0);
    }

    int s, t;
    int dep[N];
    int q[N];

    bool bfs() {
        int l = 0, r = -1;
        memset(dep, -1, sizeof dep);
        dep[s] = 0;
        q[++r] = s;
        while (l <= r) {
            int u = q[l++];
            for (int e = head[u]; e; e = nxt[e]) {
                int v = to[e];
                if (wt[e] > 0 && dep[v] == -1) {
                    dep[v] = dep[u] + 1;
                    q[++r] = v;
                }
            }
        }
        return dep[t] != -1;
    }

    int dfs(int u, int flow) {
        if (u == t || flow == 0) return flow;
        int res = 0, f = 0;
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (dep[v] == dep[u] + 1 && wt[e] > 0) {
                f = dfs(v, min(flow, wt[e]));
                res += f, wt[e] -= f, wt[e ^ 1] += f;
                flow -= f;
            }
        }
        return res;
    }

    int max_flow() {
        int res = 0;
        while (bfs())
            res += dfs(s, 0x3f3f3f3f);
        return res;
    }

    void
    set_st(int a, int b) {
        s = a, t = b;
    }
} dinic;

const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int a[55][55];
int n, m, k;

int index(int i, int j) {
    return (i - 1) * m + j;
}

int main() {
    read(n), read(m), read(k);
    for (int i = 1, x, y; i <= k; i++) {
        read(x), read(y);
        a[x][y] = 1;
    }
    int s = 0, t = n * m + 1;
    dinic.set_st(s, t);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!a[i][j]) {
                if ((i + j) & 1) {
                    dinic.link(s, index(i, j), 1);
                    for (int dir = 0; dir < 4; dir++) {
                        int x = i + dx[dir], y = j + dy[dir];
                        if (!a[x][y] && x >= 1 && x <= n && y >= 1 && y <= m) {
                            dinic.link(index(i, j), index(x, y), 1);
                        }
                    }
                } else {
                    dinic.link(index(i, j), t, 1);
                }
            }
        }
    }
    printf("%d\n", dinic.max_flow());
    return 0;
}

Problem C. 虫洞

根据题面要求,拆点建图跑最短路即可。

时间复杂度 $\mathcal O(n\log n)$

#include <bits/stdc++.h>

using namespace std;

template <typename T>
void read(T& x) {
    x = 0;
    int c = 0, f = 0;
    for (; !isdigit(c); c = getchar()) f |= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c & 15);
    x = f ? -x : x;
}

const int N = 100005, M = 600005;

int nxt[M], to[M], wt[M];
int head[N];
int edge_cnt;

void add_edge(int u, int v, int w) {
    to[++edge_cnt] = v;
    wt[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

int n, m;
int col[N], w[N], s[N];

struct Node {
    int u, dis;

    bool operator<(const Node& rhs) const {
        return rhs.dis < dis;
    }
};

priority_queue<Node> q;
bool vis[N];
int dis[N];

int bfs() {
    int s = 1;
    if (col[s] == 1) s += n;
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    dis[s] = 0, q.push((Node){s, 0});
    while (!q.empty()) {
        int u = q.top().u;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (dis[v] > dis[u] + wt[e]) {
                dis[v] = dis[u] + wt[e];
                q.push((Node){v, dis[v]});
            }
        }
    }
    return min(dis[n], dis[n + n]);
}

int main() {
    freopen("holes.in", "r", stdin);
    freopen("holes.out", "w", stdout);
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(col[i]);
    for (int i = 1; i <= n; i++) read(w[i]);
    for (int i = 1; i <= n; i++) read(s[i]);
    for (int i = 1, u, v, k; i <= m; i++) {
        read(u), read(v), read(k);
        if (col[u] != col[v]) {
            int delta = abs(w[u] - w[v]);
            add_edge(u, v, max(k - delta, 0));
            add_edge(u + n, v + n, k + delta);
        } else {
            add_edge(u, v + n, k);
            add_edge(u + n, v, k);
        }
    }
    for (int i = 1; i <= n; i++) add_edge(i, i + n, 0), add_edge(i + n, i, s[i]);
    printf("%d\n", bfs());
    return 0;
}
最后修改:2020 年 08 月 27 日 12 : 57 AM
如果觉得我的文章对你有用,请随意赞赏