梦回还 @ 2016-12-31 12:11:23
#include <cstdio>
#include <cstring>
#define max(a,b) a>b?a:b
using namespace std;
int i,j,k,n,m,v[61][4],p[61][4],a[61][50001],x,y,z,sum;
int main()
{
scanf("%d %d",&n,&m);
sum=m;
n/=10;
memset(a,-1,sizeof(a));
memset(a[0],0,sizeof(a[0]));k=0;
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&z);
x/=10;
if(z==0)
{
v[++k][1]=x;
p[k][1]=x*y;
}
else
{
sum--;
if(v[z][2]==0)
{
v[z][2]=x;
p[z][2]=x*y;
}
else
{
v[z][3]=x;
p[z][3]=x*y;
}
}
}
for(i=1;i<=sum;i++)
{
for(j=n;j>=v[i][1];j--) a[i][j]=a[i-1][j-v[i][1]]+p[i][1];
for(k=2;k<=3;++k)
{
for(j=n;j>=v[i][k];--j)
{
if(a[i][j-v[i][k]]!=-1) a[i][j]=max(a[i][j],a[i][j-v[i][k]]+p[i][k]);
}
}
for(j=0;j<=n;j++) a[i][j]=max(a[i][j],a[i-1][j]);
}
printf("%d",a[sum][n]*10);
return 0;
}
by wfstupig @ 2017-03-29 20:33:09
哈哈哈哈,因为我不是神犇,所以我是不会告诉你的!
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈呵呵哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈呵呵哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈呵呵哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈呵呵哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈呵呵哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈呵呵哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈呵呵哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈呵呵哈哈哈哈哈