43. CF-Walk the Runway

Walk the Runway

题意有点绕，在这里先简单解释一下：

有 \(n\) 个人和 \(m\) 个城市，每个人都有一个贡献值 \(p_i\)，每个人对每个城市有一个打分 \(r_{i,j}\)。现在需要选出 \(k\) 个人，并确定他们的顺序，记为 \(a_1\cdots a_k\)，这 \(k\) 个人把所有的城市都走一遍，要求对于每个城市，这 \(k\) 个人的评分都是递增的，即

在满足该条件的情况下，要求最大化贡献值之和。

数据范围 \(n\le 5000,m\le 500\)。

容易想到 dp。如果 A 可以接在 B 的后面，则必须满足对于每个维度 A 都大于 B，也就是说可以进行拓扑排序。之后就是在 DAG 上进行 dp，dp 的复杂度是 \(O(n^2)\)。

问题是有 \(m\) 个维度，如果直接进行两两比较，拓扑排序的复杂度是 \(O(n^2 m)\)，这是无法接受的。但是也没别的好办法，只好用 bitset 优化到 \(O(\frac{n^2m}{w})\)，勉强能用。

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using pii = std::pair<int, int>;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5 + 5;

using bs = std::bitset<5000>;

void solve() {
    int m, n;
    cin >> m >> n;
    vector<ll> p(n);
    for (auto& i : p)
        cin >> i;
    vector<int> ind(n);
    std::iota(ind.begin(), ind.end(), 0);
    bs all_true;
    all_true.flip();
    vector<bs> can(n, all_true);
    vector<int> r(n);
    for (int d = 0; d < m; ++d) {
        for (auto& i : r)
            cin >> i;
        sort(ind.begin(), ind.end(), [&](int x, int y) {
            return r[x] < r[y];
            });
        bs prev;
        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && r[ind[j]] == r[ind[i]]) {
                can[ind[j]] &= prev;
                ++j;
            }
            while (i < j) {
                prev[ind[i]] = true;
                ++i;
            }
        }
    }
    auto dp = p;
    for (auto i : ind) {
        for (int j = 0; j < n; ++j) {
            if (can[i][j]) {
                dp[i] = std::max(dp[i], dp[j] + p[i]);
            }
        }
    }
    cout << *std::max_element(dp.begin(), dp.end()) << endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    for (int t = 1; t <= T; ++t) {
        solve();
    }
    return 0;
}

中间求拓扑序的代码可以当做高维偏序的模板来用。