简答题
偏难
#12989
星际探险 题目描述 星际探险队计划从 n 名候选者中挑选队员组成小队,每名候选者只能入选一次。 飞船上有 m 个关键系统,第 i 名候选者的加入会对第 j 个系…
星际探险
题目描述
星际探险队计划从 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,1,000,000≤ (ai, j) ≤1,000,000。
限制:
时间限制:1000ms,内存限制:256MiB
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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;
}</pre>
这道题暂未补解析。