过_路_人 @ 2020-10-04 18:42:43
cpp
#include<bits/stdc++.h>
using namespace std;
int n, m;
int c[105][3], w[105][3], dp[32005];
int main(){
cin >> n >> m;
int cnt = 1;
for (int i = 1; i <= m; i++) {
int v, p, q;
cin >> v >> p >> q;//v 价格, p 重要度, q 从属关系
if (!q) {
c[cnt][0] = v;
w[cnt][0] = v * p;
cnt++;
}
else {
if (c[q][1]){
c[q][2] = v;
w[q][2] = v * p;
}
else {
c[q][1] = v;
w[q][1] = v * p;
}
}
}
cnt--;
for (int i = 1; i <= cnt; i++) {
for (int j = n; j >= 0; j--) {
int temp = dp[j];
if (j >= c[i][0]) {
dp[j] = dp[j - c[i][0]] + w[i][0];
for (int k = 1; k <= 2; k++) {
if (j - c[i][0] >= c[i][k])
dp[j] = max(dp[j - c[i][0] - c[i][k]] + w[i][k] + w[i][0], dp[j]);
}
if (j - c[i][0] - c[i][1] - c[i][2] >= 0) {
dp[j] = max(dp[j], dp[j - c[i][0] - c[i][1] - c[i][2]] + w[i][0] + w[i][1] + w[i][2]);
}
}
dp[j] = max(dp[j], temp);
}
}
cout << dp[n] << endl;
return 0;
}
by 圣嘉然 @ 2020-10-27 20:14:59
@过_路_人 emmm
if (!q) {
c[cnt][0] = v;
w[cnt][0] = v * p;
cnt++;
}
else {
if (c[q][1]){
c[q][2] = v;
w[q][2] = v * p;
}
else {
c[q][1] = v;
w[q][1] = v * p;
}
这里,主件和附件就对应不上了,大概是这样的:
by 圣嘉然 @ 2020-10-27 20:17:03
@过_路_人 可以这么搞
if (!q) {
c[i][0] = v;
w[i][0] = v * p;
gro[cnt++]=i;
}
记录一下第cnt
组的主件,遍历的时候
for (int t = 1; t <= cnt; t++) {
int i=gro[t];
后面就不用改了(因为还是
by 智子 @ 2021-10-11 17:59:26
@圣嘉然 感谢