题面
题意:
现在有$n$种物品,每种物品有一个买入价和售出价
现在你手头有$V$块钱
你可以买入一些物品
然后你可以用一些配料合成另一种物品
总合成次数不超过$m$次
求最大收益
其实就是两个背包$dp$
首先用一个背包$dp$算出在用不超过$i$次合成次数下得到$j$物品的最小代价
然后再来一次二维代价的背包$dp$即可1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
using namespace std;
int n, m, v, k, cost[250], val[250], op, dp1[250][250], dp[250][1005], tmp[250][50];
struct lin {
int to, cnt;
vector <int> from;
} e[250];
int main() {
scanf("%d%d%d%d", &n, &m, &v, &k);
for(int i = 1; i <= n; i++) scanf("%d%d", cost + i, val + i);
for(int i = 1; i <= m; i++) {
scanf("%d%d", &e[i].to, &e[i].cnt);
e[i].from.push_back(0);
for(int j = 1, x; j <= e[i].cnt; j++) scanf("%d", &x), e[i].from.push_back(x);
}
for(int i = 1; i <= n; i++)
for(int j = 0; j <= k; j++) dp1[i][j] = cost[i];
for(int cnt = 1; cnt <= k; cnt++)
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= e[i].cnt; j++) {
for(int t = 0; t < cnt; t++) {
tmp[j][t] = 2e9;
for(int tt = 0; tt <= t; tt++)
tmp[j][t] = min(tmp[j][t], tmp[j - 1][t - tt] + dp1[e[i].from[j]][tt]);
}
}
dp1[e[i].to][cnt] = min(dp1[e[i].to][cnt], tmp[e[i].cnt][cnt - 1]);
}
for(int i = 1; i <= n; i++)
for(int use = 0; use <= k; use++) {
for(int j = use; j <= k; j++)
for(int l = dp1[i][use]; l <= v; l++) dp[j][l] = max(dp[j][l], dp[j - use][l - dp1[i][use]] + val[i] - dp1[i][use]);
// cerr << i << ' ' << use << ' ' << dp1[i][use] << endl;
}
return cout << dp[k][v] << endl, 0;
}