首页 › 题库 › C/C++编程考级 › C/C++编程八级 › 简答题
简答题 偏难
#12840

产品研发 题目描述 一家公司正在研发一款新产品。该产品共有 K 项关键性能指标,初始时所有指标均为 0。公司的最终目标是让 每一项指标都不低于 P。 研发团队提…

产品研发

题目描述

一家公司正在研发一款新产品。该产品共有 K 项关键性能指标,初始时所有指标均为 0。公司的最终目标是让 每一项指标都不低于 P。

研发团队提出了 N 个独立的改进方案。第 i 个方案一旦实施,会同时为第 j 项指标(1≤j≤K)带来 Ai,j 的提升,但实施该方案需要投入 Ci 的研发成本。每个方案最多只能执行一次。

你需要判断:是否存在一系列方案的选择,使得所有指标均达到或超过 P?如果存在,请给出 最小的总研发成本;如果不存在,输出 −1。

输入格式

第一行,三个整数 N,K,P,分别表示方案数量、指标数量和目标阈值。

接下来 N 行,每行 K+1 个整数 Ci,Ai,1,Ai,2,…,Ai,K,分别表示第 i 个方案的成本,以及执行后各指标的提升值。

输出格式

输出一个整数,表示达成目标所需的最小总成本。若无法达成,输出 −1。

输入样例#1

4 3 5
5 3 0 2
3 1 2 3
3 2 4 0
1 0 1 4

输出样例#1

9

输入样例#2

7 3 5
85 1 0 1
37 1 1 0
38 2 0 0
45 0 2 2
67 1 1 0
12 2 2 0
94 2 2 1

输出样例#2

-1

说明提示

1≤N≤100

1≤K,P≤5

0≤Ai,j≤P(1≤i≤N, 1≤j≤K)

1≤Ci≤109(1≤i≤N)

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;climits&gt; #include &lt;algorithm&gt; using namespace std; using ll = long long; const ll INF = 1e18; int N, K, P; // 每个方案:cost,k个增量 struct Plan { ll c; vector&lt;int&gt; add; }; vector&lt;Plan&gt; pl; // 多维dp,K维,每一维0~P // 用递归式编码/解码K维下标转一维索引 int encode(const vector&lt;int&gt;&amp; st) { int res = 0; int base = 1; for (int i = 0; i &lt; K; i++) { res += st[i] * base; base *= (P + 1); } return res; } void decode(int idx, vector&lt;int&gt;&amp; st) { st.assign(K, 0); int base = 1; for (int i = 0; i &lt; K; i++) { st[i] = (idx / base) % (P + 1); base *= (P + 1); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin &gt;&gt; N &gt;&gt; K &gt;&gt; P; pl.resize(N); for (int i = 0; i &lt; N; i++) { ll c; cin &gt;&gt; c; vector&lt;int&gt; a(K); for (int j = 0; j &lt; K; j++) cin &gt;&gt; a[j]; pl[i] = {c, a}; } int stateCnt = 1; for (int i = 0; i &lt; K; i++) stateCnt *= (P + 1); vector&lt;ll&gt; dp(stateCnt, INF); vector&lt;int&gt; zero(K, 0); dp[encode(zero)] = 0; // 01背包,逐个方案更新 for (auto&amp; p : pl) { ll cost = p.c; auto&amp; add = p.add; // 倒序遍历所有状态,避免重复选取 vector&lt;ll&gt; tmp = dp; for (int idx = 0; idx &lt; stateCnt; idx++) { if (dp[idx] == INF) continue; vector&lt;int&gt; st; decode(idx, st); // 计算新状态 vector&lt;int&gt; nst(K); for (int j = 0; j &lt; K; j++) { nst[j] = min(st[j] + add[j], P); } int nidx = encode(nst); tmp[nidx] = min(tmp[nidx], dp[idx] + cost); } dp.swap(tmp); } // 目标状态:全部指标=P vector&lt;int&gt; target(K, P); ll ans = dp[encode(target)]; if (ans &gt;= INF) cout &lt;&lt; -1 &lt;&lt; endl; else cout &lt;&lt; ans &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。