A20229. 星际探险
填空题
困难
知识点
题目描述
星际探险
题目描述
星际探险队计划从 n 名候选者中挑选队员组成小队，每名候选者只能入选一次。
飞船上有 m 个关键系统，第 i 名候选者的加入会对第 j 个系统的状态值产生 (ai,j)的影响，影响可正可负。
探险安全条例要求，最终小队组成后，每个系统的状态值总和都必须不低于 0，否则飞船无法维持安全航行。
在满足该要求的前提下，希望小队的人数尽可能多，请输出这个最大人数。若不存在任何满足条件的选人方案，输出0。
输入格式
第一行：两个整数表示 n 与 m；
第二行到第 n+1 行：第 i+1 行有 m 个整数，表示 (ai,1)、(ai,2)、……、(ai,m)。
输出格式
单个整数：表示答案。
输入样例
4 3
1 1 -2
1 -2 1
-2 1 1
2 2 2输出样例
4说明提示
1≤n、m≤16，1000000≤(ai,j)≤1000000。
限制
时间限制：1000ms，内存限制：256MiB
参考答案
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
// 存储每个人对m个系统的贡献
vector<vector<long long>> a(n, vector<long long>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
int max_people = 0;
// 枚举所有子集：mask 二进制第i位=1表示选第i个人
for (int mask = 1; mask < (1 << n); ++mask) {
int cnt = __builtin_popcount(mask); // 选中的人数
if (cnt <= max_people) continue; // 剪枝：人数更少直接跳过
vector<long long> sum(m, 0);
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) { // 选了第i个人
for (int j = 0; j < m; ++j) {
sum[j] += a[i][j];
}
}
}
// 检查所有系统是否都 ≥ 0
bool ok = true;
for (long long s : sum) {
if (s < 0) {
ok = false;
break;
}
}
if (ok) {
max_people = cnt;
}
}
cout << max_people << endl;
return 0;
}
上一题
下一题