//饥民的欲死方案
#include <bits/stdc++.h>
using namespace std;
#define maxn 2010
#define maxf maxn
struct node {
int w, q;
} v1[maxn], v2[maxn];
int n, m, f[maxf], w[maxn], q[maxn];
int main() {
cin >> m >> n;
m/=10;
int x, y, z;
for (int i = 1; i <= n; i++) {
cin >> x >> y >> z;
x/=10;
if (q[i]) {
if (!v1[z].w) {
v1[z].w = x;
v1[z].q = v1[z].q*y;
} else {
v2[z].w = x;
v2[z].q = v2[z].q*y;
}
} else {
w[i] = x;
q[i] = w[i]*y;
}
}
for (int i = 1; i <= n; i++) {
for (int j = m; j >= w[i]; j--) {
f[j] = max(f[j], f[j - w[i]] + q[i]);
if (j - w[i] - v1[i].w >= 0) { //可选第一件
f[j] = max(f[j], f[j - w[i] - v1[i].w] + q[i] + v1[i].w * v1[i].q);
}
if (j - w[i] - v2[i].w >= 0) { //可选第二件
f[j] = max(f[j], f[j - w[i] - v2[i].w ] + q[i] + v2[i].w * v2[i].q);
if (j - w[i] - v1[i].w - v2[i].w >= 0) { //可选第二件
f[j] = max(f[j], f[j - w[i] - v1[i].w - v2[i].w] + q[i] + v1[i].w * v1[i].q + v2[i].w * v2[i].q);
}
}
}
}
for(int i=1;i<=n;i++){
f[0]=max(f[0],f[i]);
}
cout<<f[0]*10;
return 0;
}
graph LR
a((状态转移方程))
in1[max:选,不选] --> pd1{如果可以选自己+附件1}
pd1 --> |可以| in2[max:选自己+附件,不选]
pd1 --> |不可以| pd2{如果可以选自己+附件2}
in2 --> pd2
pd2 --> |可以| in3[max:选自己+附件2,不选]
pd2 --> |不可以| pd3{如果可以选自己+附件1+附件2}
in3 --> pd3
pd3 --> |可以| in4[max:选自己+附件1+附件2,不选]
上面这段代码不要看,现在wikioi不支持markdown流程图,支持后再说吧
共 1 条回复
金明的预算是一个分组背包, 还有的情况是两个都可以选,或者两个都不选