CF1316E Team Building

CF1316E Team Building

状压 dp

观察：假如选出了 \(p\) 个队员，那么 \(k\) 个观众一定是剩下的人中的前 \(k\) 大。

可以考虑将 \(a_i\) 从大到小排序，那么观众就是剩下的人中的一段前缀。

然后就可以考虑怎么选队员了，发现 \(p\) 很小，考虑直接状压队员。设 \(f_{i,s}\) 表示考虑完前 \(i\) 个人，已经选出的队员位置为状态 \(s\)。转移枚举第 \(i+1\) 个人是否是队员：是队员，\(f_{i+1,s|2^j}=f_{i,s}+s_{i+1,j}\)；不是队员，那么可以判断如果 \(i+1-|s|\le k\)（还要满足前 \(i\ge |s|\) ），那么一定是观众。然后就做完了。

复杂度 \(O(n2^p)\)。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10, P = 8;
int n, p, k, lim;
i64 f[N][1 << P];
struct node {
	int a, s[P];
} s[N];
bool cmp(node a, node b) {
	return a.a > b.a;
}
void solve() {
	std::cin >> n >> p >> k;
	for(int i = 1; i <= n; i++) {
		std::cin >> s[i].a;
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < p; j++) {
			std::cin >> s[i].s[j];
		}
	}

	std::sort(s + 1, s + n + 1, cmp);
	lim = (1 << p);
	for(int i = 0; i < n; i++) {
		for(int S = 0; S < lim; S++) {
			int cnt = __builtin_popcount(S);
			if(cnt > i + 1) continue;
			f[i + 1][S] = f[i][S];
			for(int j = 0; j < p; j++) {
				if((S >> j) & 1) {
					f[i + 1][S] = std::max(f[i + 1][S], f[i][S ^ (1 << j)] + s[i + 1].s[j]);
				}
			}
			if(i + 1 <= cnt + k && i >= cnt) f[i + 1][S] = std::max(f[i + 1][S], f[i][S] + s[i + 1].a);
		}
	}
	std::cout << f[n][lim - 1] << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	solve();

	return 0; //qwqqwqqwq
}