首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#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 &lt;iostream&gt; #include &lt;vector&gt; #include &lt;climits&gt; using namespace std; int main() {     ios::sync_with_stdio(false);     cin.tie(0);     int n, m;     cin &gt;&gt; n &gt;&gt; m;     // 存储每个人对m个系统的贡献     vector&lt;vector&lt;long long&gt;&gt; a(n, vector&lt;long long&gt;(m));     for (int i = 0; i &lt; n; ++i) {         for (int j = 0; j &lt; m; ++j) {             cin &gt;&gt; a[i][j];         }     }     int max_people = 0;     // 枚举所有子集:mask 二进制第i位=1表示选第i个人     for (int mask = 1; mask &lt; (1 &lt;&lt; n); ++mask) {         int cnt = __builtin_popcount(mask); // 选中的人数         if (cnt &lt;= max_people) continue;    // 剪枝:人数更少直接跳过         vector&lt;long long&gt; sum(m, 0);         for (int i = 0; i &lt; n; ++i) {             if (mask &amp; (1 &lt;&lt; i)) { // 选了第i个人                 for (int j = 0; j &lt; m; ++j) {                     sum[j] += a[i][j];                 }             }         }         // 检查所有系统是否都 ≥ 0         bool ok = true;         for (long long s : sum) {             if (s &lt; 0) {                 ok = false;                 break;             }         }         if (ok) {             max_people = cnt;         }     }     cout &lt;&lt; max_people &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。