个人觉得 *2800 有点虚高。
如果做过类似的题（比如[THUSCH2017]巧克力），应该可以想到随机映射，状压 dp 也不难想。
实际上，看到要选出 \(m\) 种不同的颜色，且 \(m\le 5\) 就可以想到将每种颜色随机映射到 \(1\) 到 \(m\) 中，这样子得出来的答案不会更优，而当答案选择的 \(m\) 种颜色恰好被映射到了不同的颜色上时会取到最优解，正确的概率为 \(\frac{m!}{m^m}\)，当 \(m=5\) 时是 \(0.0384\)。
我们可以做 \(k\) 次随机化，这样子做 \(k\) 次后还无法得出正确答案的概率为 \((1-\frac{m!}{m^m})^k\)，当 \(k\) 取 \(200\) 时只有大约 \(0.000397\) 的错误概率，可以接受。
现在 \(b\) 就只有 \(m\) 种取值，可以直接状压。
具体的，我们设 \(dp_{i,s}\) 表示选了第 \(i\) 个数，选了的颜色集合为 \(s\) 的最优方案。
转移有 \(dp_{i,s}=\max_{j=1}^{j<i}([a_j\le a_i]dp_{j,t})+c_i\)。
其中集合 \(t\) 满足 \(t\in s\wedge s\setminus t=\{b_i\}\)。
直接暴力是 \(O(n^22^m)\) 的，可以用树状数组维护前缀最大值来优化。
时间复杂度 \(O(kn2^m\log n)\)。
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int K = 200, N = 3005;
mt19937 rnd(114514);
int n, m;
int a[N], b[N], c[N], col[N];
int bit[N][1 << 5], dp[N][1 << 5], ans = -1;
void add(int x, int s, int y) {for(; x <= n; x += x & -x) bit[x][s] = max(bit[x][s], y);}
int ask(int x, int s) {int ans = 0xf3f3f3f3; for(; x; x -= x & -x) ans = max(bit[x][s], ans); return ans;}
void solve() {
memset(dp, 0xf3, sizeof dp), memset(bit, 0xf3, sizeof bit);
dp[0][0] = 0, add(1, 0, 0);
for(int i = 1; i <= n; i++) {
for(int j = 0; j < (1 << m); j++) {
if(j & (1 << col[b[i]])) continue;
int k = j | (1 << col[b[i]]);
dp[i][k] = ask(a[i], j) + c[i];
add(a[i], k, dp[i][k]);
}
ans = max(ans, dp[i][(1 << m) - 1]);
}
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
for(int i = 1; i <= K; i++) {
for(int j = 1; j <= n; j++) col[j] = rnd() % m;
solve();
}
printf("%d\n", ans);
return 0;
}