杨天祁 @ 2016-08-03 14:32:14
#include<cstdio>
#include<iostream>
using namespace std;
int n,m,x,y,z;
int f[40001],e[61][3],v[61],w[61];
int a[61],camp;
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&w[i],&v[i],&z);
if (z!=0)
{
if (e[z][1]==0)
{
e[z][1]==i;
}
else
{
e[z][2]==i;
}
}
else
{
a[++camp]=i;
}
}
for (int i=1;i<=camp;i++)
{
for (int j=n;j>=w[a[i]];j-=10)
{
if (f[j]<=f[j-w[a[i]]]+v[a[i]]*w[a[i]])
{
f[j]=f[j-w[a[i]]]+v[a[i]]*w[a[i]];
if (e[a[i]][1]!=0&&j-w[a[i]]-w[e[a[i]][1]]>=0)
{
f[j]=max(f[j],f[j-w[a[i]]-w[e[a[i]][1]]]+v[a[i]]*w[a[i]]+v[e[a[i]][1]]*w[e[a[i]][1]]);
}
if (e[a[i]][2]!=0&&j-w[a[i]]-w[e[a[i]][2]]>=0)
{
f[j]=max(f[j],f[j-w[a[i]]-w[e[a[i]][2]]]+v[a[i]]*w[a[i]]+v[e[a[i]][2]]*w[e[a[i]][2]]);
}
if (e[a[i]][1]!=0&&e[a[i]][2]!=0&&j-w[a[i]]-w[e[a[i]][1]]-w[e[a[i]][2]]>=0)
{
f[j]=max(f[j],f[j-w[a[i]]-w[e[a[i]][1]]-w[e[a[i]][2]]]+v[a[i]]*w[a[i]]+v[e[a[i]][1]]*w[e[a[i]][1]]+v[e[a[i]][2]]*w[e[a[i]][2]]);
}
}
}
}
printf("%d",f[n]);
return 0;
}by 2015wanghongyu @ 2016-08-10 08:33:33
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long n,m;
long long newv[55000],newp[55000];
long long v[55000],p[55000],q[55000];
long long f[55000];
long long calc(long long k)
{
long long i,j,x;
x=1;
newv[1]=v[k];
newp[1]=p[k];
for(i=1;i<=m;++i)
if(q[i]==k)
{
for(j=1;j<=x;++j)
{
newv[j+x]=newv[j]+v[i];
newp[j+x]=newp[j]+p[i];
}
x=x*2;
}
return x;
}
int main()
{
long long i,j,k;
scanf("%lld%lld",&n,&m);
for(i=1;i<=m;++i)
{
scanf("%lld%lld%lld",&v[i],&p[i],&q[i]);
p[i]=p[i]*v[i];
}
memset(f,0,sizeof(f));
for(i=1;i<=m;++i)
{
if(q[i]==0) //continue;
for(j=n;j>=1;--j)
for(k=1;k<=calc(i);++k)
if(j>=newv[k])
if(f[j]<f[j-newv[k]]+newp[k])
f[j]=f[j-newv[k]]+newp[k];
}
cout<<f[n]<<endl;
return 0;
}