wozolu @ 2018-08-17 21:51:06
#include<cstdio>
#include<iostream>
#include<cmath>
#include<memory.h>
using namespace std;
/*输入文件budget.in 的第1行,为两个正整数,用一个空格隔开:N m
(其中N(<32000)表示总钱数,m(<60)为希望购买物品的个数。)
从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,
每行有3个非负整数 v p q(其中v表示该物品的价格(v<10000),
p表示该物品的重要度(1~5),q表示该物品是主件还是附件。
如果q=0,表示该物品为主件,如果q>0,表示该物品为附件,q是所属主件的编号)
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
*/
int v[100],p[100],q,d[100][100],pj[100],zj,f[100];
int main(){
int n,m;
cin>>n>>m;
n/=10;
for(int i=1;i<=m;i++){
cin>>v[i]>>p[i]>>q;
p[i]*=v[i];
v[i]/=10;
d[q][++d[q][0]]=i;
}
for(int i=1;i<=d[0][0];i++){
int o=d[0][i];
for(int j=n;j>=v[i];j--){
f[j]=max(f[j-v[o]]+p[o],f[j]);
if(j>v[d[o][1]]+v[o])f[j]=max(f[j-v[o]-v[d[o][1]]]+p[o]+p[d[o][1]],f[j]);
if(j>v[d[o][2]]+v[o])f[j]=max(f[j-v[o]-v[d[o][2]]]+p[o]+p[d[o][2]],f[j]);
if(j>v[d[o][1]]+v[d[o][2]]+v[o])f[j]=max(f[j-v[o]-v[d[o][2]]-v[d[o][1]]]+p[o]+p[d[o][1]]+p[d[o][2]],f[j]);
}
}
cout<<f[n];
return 0;
}
感觉自己打的和一个题解也没什么区别啊…