nuo_x @ 2024-02-03 16:28:34
#include<bits/stdc++.h>
using namespace std;
struct stu{
int w[5],c[5],total;
}a[35000];
int n,m,q,v,p;
int cnt;
int f[100][35000];
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
{
cin>>v>>p>>q;
if(q==0)
{
a[i].total=1;
a[i].w[1]=v;
a[i].c[1]=v*p;
}
else if(a[q].total==1)
{
a[q].total=2;
a[q].w[2]=a[q].w[1]+v;
a[q].c[2]=a[q].c[1]+v*p;
}
else
{
a[q].total=3;
a[q].w[3]=a[q].w[1]+v;
a[q].c[3]=a[q].c[1]+v*p;
a[q].total=4;
a[q].w[4]=a[q].w[2]+v;
a[q].c[4]=a[q].c[2]+v*p;
}
}
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
for(int k=1;k<=a[i].total;k++)
if(j>=a[i].w[k])
f[i][j]=max(f[i][j],f[i-1][j-a[i].w[k]]+a[i].c[k]);
}
cout<<f[n][m];
return 0;
}
by _fwTransform_ @ 2024-02-23 10:00:32
@nuo_x hack点用P1060 开心的金明的代码能过,也就是没有依赖的情况
by _fwTransform_ @ 2024-02-23 10:13:59
@ReturnOrContinue 是不受依赖影响的情况