lako @ 2016-12-09 22:44:58
#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int v[1000],p[1000];
int vq[100][10];
int pq[100][10];
int num[1000];
int f[40000];
#define max(a,b) (((a)>(b))?(a):(b))
int main(){
//freopen("testdata.in","r",stdin);
cin>>n>>m;
int qq;
int a,b;
int mm=0;
for(int i=1;i<=m;i++){
cin>>a>>b>>qq;
if(qq==0){
mm++;
v[mm]=a;
p[mm]=b;
}
else{
num[qq]++;
vq[qq][num[qq]]=a;
pq[qq][num[qq]]=b;
}
}
for(int i=1;i<=mm;i++){
for(int j=n;j>=0;j--){
if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+v[i]*p[i]);
if(j>=v[i]+vq[i][1])f[j]=max(f[j],f[j-v[i]-vq[i][1]]+v[i]*p[i]+vq[i][1]*pq[i][1]);
if(j>=v[i]+vq[i][2])f[j]=max(f[j],f[j-v[i]-vq[i][2]]+v[i]*p[i]+vq[i][2]*pq[i][2]);
if(j>=v[i]+vq[i][1]+vq[i][2])f[j]=max(f[j],f[j-v[i]-vq[i][1]-vq[i][2]]+v[i]*p[i]+vq[i][1]*pq[i][1]+vq[i][2]*pq[i][2]);
}
}
cout<<f[n];
return 0;
}
by lako @ 2016-12-10 00:18:41
问题解决了,是我的变量绑定物品编号不对。改成这样
for(int i=1;i<=m;i++){
cin>>a>>b>>qq;
if(qq==0){
v[i]=a;
p[i]=b*a;
}
else{
num[qq]++;
vq[qq][num[qq]]=a;
pq[qq][num[qq]]=b*a;
}
}
这样就对了,惨痛的教训