htomo111 @ 2022-11-20 20:55:08
感觉没问题啊???
样例过了只得10pts
#include<iostream>
using namespace std;
struct node
{
int lkid,rkid;
bool fl=true;
}s[35000];
int n,f[35000],w[35000],v[35000],h;
int main()
{
cin>>n>>h;
for(int i=1;i<=h;i++)
{
int a;
cin>>w[i]>>v[i]>>a;
v[i]*=w[i];
if(a!=0)
{
if(s[a].lkid>0)s[a].rkid=i;
else s[a].lkid=i;
s[i].fl=false;
}
}
for(int i=1;i<=h;i++)
{
if(s[i].fl==false)continue;
for(int j=n;j>=w[i];j--)
{
if(j>=w[i])f[j]=max(f[j],f[j-w[i]]+v[i]);
if(j>=w[i]+w[s[i].lkid])f[j]=max(f[j],f[j-w[i]-w[s[i].lkid]]+v[i]+v[s[i].lkid]);
if(j>=w[i]+w[s[i].rkid])f[j]=max(f[j],f[j-w[i]-w[s[i].rkid]]+v[i]+v[s[i].rkid]);
if(j>=w[i]+w[s[i].lkid]+w[s[i].rkid])f[j]=max(f[j],f[j-w[i]-w[s[i].lkid]]+v[i]+v[s[i].lkid]+v[s[i].rkid]);
}
}
cout<<f[n];
return 0;
}