yzong @ 2017-07-06 10:42:05
第四个点过不去了
#include<iostream>
#include<stdio.h>
using namespace std;
int top,top2,m,n,v[61],p[61],q[61],cun1[1001],cun2[201],s[61][32001],ans[61],top3;
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&v[i],&p[i],&q[i]);
for(int i=1;i<=n;i++)
{
if(q[i]==0)
{
top++;
cun1[top]=v[i];
cun2[top]=v[i]*p[i];
for(int j=1;j<=n;j++)
{
if(q[j]==i)
{
int jl=top;
for(int k=top2+1;k<=jl;k++)
{
top++;
cun1[top]=cun1[k]+v[j];
cun2[top]=cun2[k]+v[j]*p[j];
}
}
}
top3++;
ans[top3]=top-top2;
top2=top;
}
}
top2=0;
for(int i=1;i<=top3;i++)
{
for(int j=1;j<=ans[i];j++)
{
top2++;
for(int k=0;k<=m;k++)
{
if(k>=cun1[top2])
s[i][k]=max(max(s[i-1][k],s[i][k]),s[i-1][k-cun1[top2]]+cun2[top2]);
}
}
}
printf("%d",s[top3][m]);
return 0;
}