pqy000 @ 2018-09-19 11:59:06
#include<iostream>
#include<algorithm>
using namespace std;
#define MMAX 65
#define NMAX 32005
int v[MMAX][3], p[MMAX][3], N, M;
int thing[NMAX];
int cost2(int index, int x) { return v[index][0] + v[index][x]; }
int cost3(int index, int x, int y)
{ return v[index][0] + v[index][x] + v[index][y]; }
int value(int index, int x){ return v[index][x] * p[index][x]; }
int main() {
scanf("%d%d", &N, &M);
int _v, _p, _q;
int num = 1;
for(int i = 1; i <= M; i++) {
scanf("%d%d%d", &_v, &_p, &_q);
if(_q == 0) {
v[num][0] = _v; p[num][0] = _p;
num += 1;
} else {
if(v[_q][1] == 0) {
v[_q][1] = _v; p[_q][1] = _p;
} else {
v[_q][2] = _v; p[_q][2] = _p;
}
}
}
for(int i = 1; i < num; i++) {
for(int j = N; j >= 0; j--) {
if(j >= v[i][0]){
thing[j] = max(thing[j], thing[j - v[i][0]] + value(i, 0) ); }
if(j >= (v[i][0] + v[i][1]) && v[i][1] != 0 ) {
thing[j] = max(thing[j], thing[j - v[i][0] - v[i][1] ] + v[i][0] * p[i][0] + v[i][1] * p[i][1]);
}
if(j >= (v[i][0] + v[i][2]) && v[i][2] != 0 ) {
thing[j] = max(thing[j], thing[j - v[i][0] - v[i][2]] + v[i][0] * p[i][0] + v[i][2] * p[i][2]);
}
if(j >= (v[i][0] + v[i][1] + v[i][2]) && v[i][1] != 0 && v[i][2] != 0) {
thing[j] = max(thing[j], thing[j - (v[i][0] + v[i][1] + v[i][2])]
+ v[i][0] * p[i][0] + v[i][1] * p[i][1] + v[i][2] * p[i][2]);
}
}
}
/*
for(int i = 1; i < num; i++) {
for(int j = 0; j < 3; j++) {
printf("(%d %d) ", v[i][j], p[i][j]);
}
printf("\n");
} */
//for(int i = 1; i <= N; i++) { printf("%d %d\n", i, thing[i]); }
printf("%d\n", thing[N]);
return 0;
}
转移方程也写好了....在本题中我只存储了主件,附件直接挂靠在主件上,并统计遍历主件的数量num,但结果是错的...我想了解下怎样改进,谢谢大佬, 不过的样例如下:
//input
2000 10
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5
//output
7430
//程序错误输出
7200
谢谢诸位大佬~