A17498. 产品研发
填空题
困难
知识点
题目描述
产品研发
题目描述
一家公司正在研发一款新产品。该产品共有 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）
参考答案
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int N, K, P;
// 每个方案：cost，k个增量
struct Plan {
ll c;
vector<int> add;
};
vector<Plan> pl;
// 多维dp，K维，每一维0~P
// 用递归式编码/解码K维下标转一维索引
int encode(const vector<int>& st) {
int res = 0;
int base = 1;
for (int i = 0; i < K; i++) {
res += st[i] * base;
base *= (P + 1);
}
return res;
}
void decode(int idx, vector<int>& st) {
st.assign(K, 0);
int base = 1;
for (int i = 0; i < K; i++) {
st[i] = (idx / base) % (P + 1);
base *= (P + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> K >> P;
pl.resize(N);
for (int i = 0; i < N; i++) {
ll c; cin >> c;
vector<int> a(K);
for (int j = 0; j < K; j++) cin >> a[j];
pl[i] = {c, a};
}
int stateCnt = 1;
for (int i = 0; i < K; i++) stateCnt *= (P + 1);
vector<ll> dp(stateCnt, INF);
vector<int> zero(K, 0);
dp[encode(zero)] = 0;
// 01背包，逐个方案更新
for (auto& p : pl) {
ll cost = p.c;
auto& add = p.add;
// 倒序遍历所有状态，避免重复选取
vector<ll> tmp = dp;
for (int idx = 0; idx < stateCnt; idx++) {
if (dp[idx] == INF) continue;
vector<int> st;
decode(idx, st);
// 计算新状态
vector<int> nst(K);
for (int j = 0; j < 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<int> target(K, P);
ll ans = dp[encode(target)];
if (ans >= INF) cout << -1 << endl;
else cout << ans << endl;
return 0;
}
上一题
下一题