简单的01背包，只不过多了分情况讨论
只需要分情况讨论，然后最后做01背包的时候进行多种情况讨论就好
c++
#include<cstdio>
#include<cstring>
struct node{int w[4],v[4],c;}s[61];
int n,m;
int k[61];
int maxx(int x,int y){return x>y?x:y;}
int main()
{
scanf("%d %d",&n,&m);
n=n/10;
int j=1;
for(int i=1;i<=m;i++)
{
int v,p,q;
scanf("%d %d %d",&v,&p,&q);
v=v/10;
if(q==0)
{
s[j].v[0]=v;
s[j].w[0]=v*p;
s[j].c=1;
k[i]=j;
j++;
}
else
{
q=k[q];
if(s[q].c==1)//如果我目前只有一种方案也就是这个东西目前没有附件
{
s[q].v[1]=s[q].v[0]+v;//多加入一种新的情况
s[q].w[1]=s[q].w[0]+v*p;
s[q].c=2;
}
else//否则就是只有两种附件了
{
s[q].v[2]=s[q].v[0]+v;// 那就分两种情况，只买主件和附件2
s[q].w[2]=s[q].w[0]+v*p;
s[q].v[3]=s[q].v[1]+v;//两种附件都买
s[q].w[3]=s[q].w[1]+v*p;
s[q].c=4;//然后把方案数量改成4个
}
}
}
int f[3201];memset(f,0,sizeof(f));
for(int i=1;i<j;i++) //照常做01背包，只不过多了分情况讨论而已
{
for(int k=n;k>0;k--)//分当前的情况数进行讨论
{
for(int x=0;x<s[i].c;x++)
{
if(k>=s[i].v[x])
f[k]=maxx(f[k],f[k-s[i].v[x]]+s[i].w[x]);
}
}
}
printf("%d",f[n]*10);
}


测试数据 #0: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 572 KiB, score = 10
Accepted, time = 0 ms, mem = 572 KiB, score = 100
题解+代码

嘿嘿,在VIJOS上的第一道题目。

各位表鄙视我啊

简单动归

我二十分！！

请大家鄙视！！

T-T