矛盾体 @ 2017-11-01 20:33:59
#include<iostream>
#include<fstream>
using namespace std;
//ifstream fin("testdata.in");
//ofstream fout("out.txt");
int s[32010],goods[65][4],o[65],value[65][4],a[65],b[65],c[65];
int main()
{
int N,m,j=0;
cin>>N>>m;
for(int i=1;i<=m;i++)
{
cin>>a[i]>>b[i]>>c[i];
if(c[i]==0)
{
j++;
goods[j][0]=a[i];
value[j][0]=a[i]*b[i];
o[i]=j;
}
}
for(int i=1;i<=m;i++)
{
if(c[i])
{
if(!goods[o[c[i]]][1])
{
goods[o[c[i]]][1]=goods[o[c[i]]][0]+a[i];
value[o[c[i]]][1]=value[o[c[i]]][0]+a[i]*b[i];
}
else
{
goods[o[c[i]]][2]=goods[o[c[i]]][0]+a[i];
value[o[c[i]]][2]=value[o[c[i]]][0]+a[i]*b[i];
goods[o[c[i]]][3]=goods[o[c[i]]][1]+a[i];
value[o[c[i]]][3]=value[o[c[i]]][1]+a[i]*b[i];
}
}
}
for(int i=1;i<=j;i++)
for(int t=0;t<=3;t++)
for(int k=N;k>=0;k--)
{
if(k>=goods[i][t])
s[k]=max(s[k],s[k-goods[i][t]]+value[i][t]);
}
cout<<s[N];
return 0;
}
这个为什么才20分。。。