ARC006 C問題：積み重ね

問題. 積み重ね

個のダンボールがある．ダンボールは 1 から N まで番号付けされており， 番目のダンボールの重さは である．1番目のダンボールから順番に部屋に収納する．このとき， に対して なら 番目のダンボールの上に 番目のダンボールを重ねることができる．ダンボールの山の数の最小値を答えよ．

制約： ，　

解法1．DAGの最小道被覆問題

各ダンボールを頂点として， 番目のダンボールの上に 番目のダンボールを重ねることができるとき弧 を張ることによって有向グラフ を構成する． 上の1つの有向道とダンボールの山が対応するので，この問題は最小道被覆問題となる．また， は明らかに DAG なので二部グラフの最大マッチング問題に帰着することができる．
　DAGの最小道被覆問題 - 忘れても大丈夫
したがって， 時間で有向グラフを構成して，フォード・ファルカーソン法を用いて二部グラフの最大マッチング問題を 時間で解く（最大流は 以下）．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

template<typename Weight>
struct FordFulkerson {
    using weight_type = Weight;

    struct Edge {
        int src, dst, rev;
        Weight cap;
        Edge(int f, int t, Weight c, int r) :
            src(f), dst(t), rev(r), cap(c) {}
    };

    int n;
    std::vector<std::vector<Edge>> adj;
    const Weight INF;

    explicit FordFulkerson(int _n, Weight inf = std::numeric_limits<Weight>::max() / 10)
        : n(_n), adj(n), INF(inf) {}

    void add_arc(const int src, const int dst, const Weight cap) {
        adj[src].emplace_back(Edge(src, dst, cap, adj[dst].size()));
        adj[dst].emplace_back(Edge(dst, src, 0, adj[src].size() - 1));
    }

    void add_edge(const int src, const int dst, const Weight cap) {
        add_arc(src, dst, cap);
        add_arc(dst, src, cap);
    }

    Weight MaximumFlow(const int s, const int t) {
        Weight flow = 0;
        while (true) {
            std::vector<bool> visited(n, false);
            Weight f = Dfs(s, INF, t, visited);
            if (f <= 0) break;
            flow += f;
        }
        return flow;
    }

    Weight Dfs(int v, Weight f, const int t, std::vector<bool> &visited) {
        if (v == t) return f;

        visited[v] = true;
        for (auto &&e : adj[v]) {
            if (!visited[e.dst] && 0 < e.cap) {
                Weight d = Dfs(e.dst, std::min(f, e.cap), t, visited);
                if (0 < d) {
                    e.cap -= d;
                    adj[e.dst][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
};


int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    int N;
    cin >> N;

    vector<int> w(N);
    for (auto &w_i : w) cin >> w_i;

    const int s = 0, t = 2 * N + 1;
    FordFulkerson<int> g(2 * N + 2);
    for (int v = 1; v <= N; ++v) {
        g.add_arc(s, v, 1);
        g.add_arc(v + N, t, 1);

        for (int u = v + 1; u <= N; ++u) {
            if (w[v - 1] >= w[u - 1])
                g.add_arc(v, u + N, 1);
        }
    }

    cout << N - g.MaximumFlow(s, t) << endl;

    return 0;
}

解法2．貪欲法（解法1の高速化）

解法1で構成される二部グラフは下の図のように弧の端点集合に関して包含関係があるので， 番目のダンボールはまだ選ばれていないダンボールで重さが 以下で の右側にある中で最も左にあるものを貪欲に選択することが最適となる（だぶん何か名前がついていた気がするけど・・・）．
　　　　　　　　　　

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    int N;
    cin >> N;

    vector<int> w(N);
    for (auto &w_i : w) cin >> w_i;

    int num_box = 0;
    vector<bool> used(N, false);
    for (int i = 0; i < N; ++i) {
        if (used[i]) continue;

        ++num_box;
        used[i] = true;
        for (int j = i + 1, prev = i; j < N; ++j) {
            if (!used[j] && w[prev] >= w[j]) {
                prev = j;
                used[j] = true;
            }
        }
    }

    cout << num_box << endl;

    return 0;
}

貪欲法の証明は最小道被覆からの帰着だと簡単だけど，経由しない方法だと難しい気がする． そんなことは無かった．