蒟蒻求助……

斗神·君莫笑 @ 2018-09-10 17:48:02

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int w,v;
}a[110][2];
int yingshe[110];
int f[32010];
int main(){
    int m,n,cnt=0;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;++i){
        int w,v,from;
        scanf("%d%d%d",&w,&v,&from);
        from=yingshe[from];
        if(from>0)
            if(!a[from][1].w)
                a[from][1].w=w,a[from][1].v=v*w;
            else
                a[from][2].w=w,a[from][2].v=v*w;
        else
            yingshe[i]=++cnt,a[cnt][0].w=w,a[cnt][0].v=v*w;
    }
    for(int i=1;i<=cnt;++i)
        for(int j=m;j>=a[i][0].w;--j){
            f[j]=max(f[j],f[j-a[i][0].w]+a[i][0].v);
            if(j>=a[i][0].w+a[i][1].w)f[j]=max(f[j],f[j-a[i][0].w-a[i][1].w]+a[i][0].v+a[i][1].v);
            if(j>=a[i][0].w+a[i][2].w)f[j]=max(f[j],f[j-a[i][0].w-a[i][2].w]+a[i][0].v+a[i][2].v);
            if(j>=a[i][0].w+a[i][1].w+a[i][2].w)f[j]=max(f[j],f[j-a[i][0].w-a[i][1].w-a[i][2].w]+a[i][0].v+a[i][1].v+a[i][2].v);
        }
    printf("%d",f[m]);
    return 0;
}

by C201914 @ 2018-09-10 18:29:08

看着脑阔痛这是我的代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define INF 0x3f3f3f3f
#define MAXN 1000
using namespace std;
int n,m,w[61],v[61],son[61][3]={0},f[32000],top=0,list[61]; 
int fa[61];
inline long long read()
{
    int bj=1,res=0;char c=0;
    while(c<'0'||c>'9'){if(c=='-')bj=-1;c=getchar();}
    while(c>='0'&&c<='9'){res=res*10+c-48;c=getchar();}
    return bj*res;
}
int main()
{
//  freopen("t1.in","r",stdin);
//  freopen("t1.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        w[i]=read();v[i]=read();fa[i]=read();
        if(fa[i])son[fa[i]][++son[fa[i]][0]]=i;
        else list[i]=top,top=i;
    }
    for(int i=1;i<=m;i++)
        for(int j=n;j>=w[i];j--)
        {
            if(fa[i])continue;
            f[j]=max(f[j],f[j-w[i]]+w[i]*v[i]);
            if(son[i][0]>=1&&j>=w[i]+w[son[i][1]])f[j]=max(f[j],f[j-w[i]-w[son[i][1]]]+w[i]*v[i]+w[son[i][1]]*v[son[i][1]]);
            if(son[i][0]==2)
            {
                if(j>=w[i]+w[son[i][2]])f[j]=max(f[j],f[j-w[i]-w[son[i][2]]]+w[i]*v[i]+w[son[i][2]]*v[son[i][2]]);
                if(j>=w[i]+w[son[i][1]]+w[son[i][2]])f[j]=max(f[j],f[j-w[i]-w[son[i][1]]-w[son[i][2]]]+w[i]*v[i]+w[son[i][1]]*v[son[i][1]]+w[son[i][2]]*v[son[i][2]]);
            }
        }
    printf("%d",f[n]);
    return 0;
} 

by 斗神·君莫笑 @ 2018-09-10 18:34:03

@C201914 蟹蟹QAQ