\(Solution\)
考虑 dp。
观察数据范围，\(n,k\leq 500\) 的数据几乎明示了同阶下 \(\Theta(n^3)\) 的算法了。那么直接往这里考虑。
设 \(f_{i,j}\) 为当前是第 \(i\) 中颜色，且已经选了 \(j\) 种颜色的最大值。
那么有以下转移方程：
\[f_{i,k}=\max^{i-1}_{j=1} cmp(i,j)\land f_{j,k-1} \]其中 \(cmp\) 函数为判断两个颜色是否有交叉段，即是否呈单调不下降序列。当然这两个颜色必须存在。
那么我们记两个数组 \(front,back\) 为当前颜色最早和最后出现的位置即可。
\(\mathcal{Code}\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 500 + 5;
int a[N], b[N], up[N], down[N], ans, f[N][N];
signed main() {
auto read = [&]() -> auto {
int x = 0, m = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') m = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - 48;
ch = getchar();
}
return x * m;
};
function<void(int)> write = [&](int x) {
if (x < 0) {
putchar('-');
write(-x);
return ;
}
if (x >= 10) write(x / 10);
putchar(x % 10 + '0');
};
auto writeln = [&](int x) -> auto {
write(x), putchar('\n');
};
auto writesp = [&](int x) -> auto {
write(x), putchar(' ');
};
int n = read(), m = read();
for(int i = 1; i <= n; i ++) {
a[i] = read();
if(!up[a[i]]) up[a[i]] = i;
}
for(int i = n; i; i --) if(!down[a[i]]) down[a[i]] = i;
for(int i = 1; i <= n; i ++) b[i] = read();
for(int i = 1; i <= n; i ++) {
f[i][1] = b[i];
for(int j = 1; j < i; j ++) {
if(down[j] > up[i] || !down[j] || !up[i]) continue;
for(int k = 2; k <= m; k ++) {
if(!f[j][k - 1]) continue;
f[i][k] = max(f[i][k], f[j][k - 1] + b[i]);
}
}
ans = max(ans, f[i][m]);
}
if(!ans) cout << -1 << '\n';
else cout << ans << '\n';
return 0;
}