题意：给定一个物品序列。每个物品有 \(m\) 种属性和一个收益（第 \(i\) 个物品的第 \(j\) 种属性为 \(r_{j,i}\)）。你需要从原序列中取出几个物品（可以乱序取），并给这些取出的物品安排顺序，使得新的物品序列满足：对于任意 \(i,j[i<j]\)，都有 \(i\) 的任意指标都比 \(j\) 小。
\(O(n^2m)\) 的朴素 \(\text{DP}\) 比较简单，我们按照任意一个属性（指标）对序列进行排序。之后设 \(f_i\) 为 \(i\) 强制选时，\(1\to i\) 这些物品能获得的最大价值。转移则是通过偏序关系转移——即 \(j\) 能转移到 \(i\) 当且仅当 \(j<i\) 且 \(\forall k,r_{j,k}<r_{i,k}\)。
之后考虑优化转移时判断的过程。我们对 \(j\) 能否转移到 \(i\) 进行统一的预处理。具体的，我们对于每一个属性分别计算有哪些 \(j\) 的当前属性比 \(i\) 小，然后把多个属性的结果进行与运算，得到最终的结果。这一整个过程都可以用 \(\text{bitset}\) 进行优化。
总时间复杂度为 \(O(\frac{mn^2}{w}+nm\log n)\)，\(w\) 取 \(32\)。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
typedef long long ll;
const int N = 5010, M = 510;
int m, n, c, r[N][M], id[N];
ll ans, f[N];
bitset<N> now, b[N];
int cmp(int i, int j){return r[i][c] < r[j][c];}
int main(){
scanf("%d%d", &m, &n);
FL(i, 1, n) id[i] = i, b[i].set();
FL(j, 0, m) FL(i, 1, n) scanf("%d", &r[i][j]);
FL(k, 1, m){
now.reset(), now[0] = 1, c = k;
sort(id + 1, id + n + 1, cmp);
FL(i, 1, n){
int j = i;
while(j < n && r[id[j + 1]][k] == r[id[i]][k]) j++;
FL(l, i, j) b[id[l]] &= now;
FL(l, i, j) now[id[l]] = 1; i = j;
}
}
sort(id + 1, id + n + 1, cmp);
FL(i, 1, n) FL(j, 0, i - 1) if(b[id[i]][id[j]])
f[i] = max(f[i], f[j] + r[id[i]][0]);
FL(i, 1, n) ans = max(ans, f[i]);
printf("%lld", ans);
return 0;
}