Alien_worm @ 2018-05-05 23:38:24
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
int v[3], p[3]; // v[0],p[0]主件,v[1],v[2],p[1],p[2]附件
int fj; // 附件个数
}x[65];
int dp[32222];
int main(){
int n, m, re, cnt = 0, f = 1;
cin >> n >> m;
for(int i = 0; i < m; i++){
int v, p, q;
cin >> v >> p >> q;
if(q == 0){
x[cnt].v[0] = v;
x[cnt].p[0] = v * p;
re = cnt;
f = 1;
cnt++;
}
else{
x[re].v[f] = v;
x[re].p[f] = v * p;
x[re].fj++;
f++;
}
}
for(int i = 0; i < cnt; i++){
for(int j = n; j >= x[i].v[0]; j--){
if(x[i].fj == 0){ // 只有主件
dp[j] = max(dp[j], dp[j-x[i].v[0]] + x[i].p[0]);
}
else if(x[i].fj == 1){ // 有一个附件
dp[j] = max(dp[j], dp[j-x[i].v[0]] + x[i].p[0]);
if(j-x[i].v[0]-x[i].v[1] >= 0)
dp[j] = max(dp[j], dp[j-x[i].v[0]-x[i].v[1]] + x[i].p[0] + x[i].p[1]);
}
else if(x[i].fj == 2){ // 有两个附件
dp[j] = max(dp[j], dp[j-x[i].v[0]] + x[i].p[0]);
if(j-x[i].v[0]-x[i].v[1] >= 0) // 选主件和附件一
dp[j] = max(dp[j], dp[j-x[i].v[0]-x[i].v[1]] + x[i].p[0] + x[i].p[1]);
if(j-x[i].v[0]-x[i].v[2] >= 0) // 选主件和附件二
dp[j] = max(dp[j], dp[j-x[i].v[0]-x[i].v[2]] + x[i].p[0] + x[i].p[2]);
if(j-x[i].v[0]-x[i].v[1]-x[i].v[2] >= 0) // 选主件和附件一附件二
dp[j] = max(dp[j], dp[j-x[i].v[0]-x[i].v[1]-x[i].v[2]] + x[i].p[0] + x[i].p[1] + x[i].p[2]);
}
}
}
cout << dp[n] << endl;
}
by WorldBest丶牛顿 @ 2018-05-06 06:43:30
感觉是不是前面f有问题,如果两个主件相同的附件不相邻的话就会出错
不如直接用fj代替f存数组