定义：\(A_c\) 表示颜色为 \(c\) 的物品集合，\(g \otimes S\) 表示背包 \(g\) 中插入集合 \(S\) 中的所有物品后的新背包。
刚开始想的是对于每种颜色，求出各自背包，然后进行 \(lim_c\) 次 \(O({lim_w}^2)\) 的合并。
显然 T 了，考虑漏了什么：本来操作 \(g \otimes S\) 是 \(O(|g| \cdot |s|)\) 的，当物品个数小于背包大小时，这种合并方式更加合理。
那么就好办了，设 \(f_{c,k}\) 表示考虑前 \(c\) 种颜色，使用 \(k\) 种颜色时的背包（下文中，前一维滚动掉，但是这样 \(k\) 需要倒序枚举）。
枚举使用 \(c\) 颜色去更新整个 \(f\)，则 \(f_k \otimes A_c \to f_{k+1}\)。
因为物品总数为 \(n\)，所以这么做是 \(O(nm\cdot lim_c)\) 的。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
auto debug(auto ...b){((cerr << b << ' ') , ...); cerr << '\n';}
#else
#define debug(...) 0717
#endif
using ll = long long;
using uint = unsigned;
const int INF = 0x3F3F3F3F;
const ll INFl = 0x3F3F3F3F3F3F3F3F;
#define all(x) x.begin(),x.end()
#define r_all(x) x.rbegin(),x.rend()
const int N = 105;
const int S = 10005;
const int C = 53;
using gd = array<int , 2>;
int n , lim_w , lim_c;
vector<gd> a[C];
int f[C][S] , g[S];
signed main() {
#ifdef LOCAL
#elif defined(ONLINE_JUDGE)
#else
#endif
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> lim_w >> lim_c;
for(int i = 1; i <= n; ++ i){
int w , v , c;
cin >> w >> v >> c;
a[c].push_back({w , v});
}
for(int c = 1; c <= 50; ++ c){
for(int k = lim_c - 1; k >= 0; -- k){
copy(f[k] , f[k] + lim_w + 1 , g);
for(auto [w , v] : a[c]) for(int j = lim_w; j >= 0; -- j){
if(j + w <= lim_w) g[j + w] = max(g[j + w] , g[j] + v);
}
for(int j = 0; j <= lim_w; ++ j){
f[k + 1][j] = max(f[k + 1][j] , g[j]);
}
}
}
int ans = 0;
for(int k = 1; k <= lim_c; ++ k){
ans = max(ans , *max_element(f[k] , f[k] + lim_w + 1));
}
cout << ans << '\n';
return 0;
}