电路布线

std::vector<std::vector<int>> MNS(std::vector<int>& C) {
    int n = C.size();
    std::vector<std::vector<int>> s(n + 1, std::vector<int>(n + 1, 0));
    for (int j = 0; j < C[1]; j++) {
        s[1][j] = 0;
    }
    for (int j = C[1]; j <= n; j++) {
        s[1][j] = 1;
    }
    for (int i = 2; i < n; i++) {
        for (int j = 0; j < C[i]; j++) {
            s[i][j] = s[i - 1][j];
        }
        for (int j = C[i]; j <= n; j++) {
            s[i][j] = std::max(s[i - 1][j], s[i - 1][C[i] - 1] + 1);
        }
    }
    s[n][n] = std::max(s[n - 1][n], s[n - 1][C[n] - 1] + 1);
}

std::vector<int> Traceback(std::vector<int>& C, std::vector<std::vector<int>>& s) {
    int n = C.size();
    std::vector<int> Net;
    for (int i = n; i > 1; i--) {
        if (s[i][j] != s[i - 1][j]) {
            Net.push_back(i);
            j = C[i] - 1;
        }
        if (j >= C[1]) {
            Net.push_back(1);
        }
    }
}