题意有点绕，在这里先简单解释一下：
有 \(n\) 个人和 \(m\) 个城市，每个人都有一个贡献值 \(p_i\)，每个人对每个城市有一个打分 \(r_{i,j}\)。现在需要选出 \(k\) 个人，并确定他们的顺序，记为 \(a_1\cdots a_k\)，这 \(k\) 个人把所有的城市都走一遍，要求对于每个城市，这 \(k\) 个人的评分都是递增的，即
\[\large r_{i,a_1}\lt r_{i,a_2}\lt \cdots \lt r_{i,a_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;
}
中间求拓扑序的代码可以当做高维偏序的模板来用。