Shik__Utau @ 2019-09-02 21:14:18

#include<bits/stdc++.h>
using namespace std;
int n,m,w[65],v[65],s[65][3]={0},f[32005];
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d%d%d",&v[i],&w[i],&x);
        w[i]*=v[i];
        if(x)s[x][++s[x][0]]=i,s[i][0]=3;
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++){
        if(s[i][0]==3)continue;
        int maxx=v[i];
        if(s[i][0]>=1)maxx+=v[s[i][1]];
        if(s[i][0]==2)maxx+=v[s[i][2]];
        for(int j=m;j>=maxx;j--){
            int minn=f[j];
            if(f[j-v[i]]+w[i]>f[j])f[j]=f[j-v[i]]+w[i];
            if(s[i][0]==1&&f[j-v[i]-v[s[i][1]]]+w[i]+w[s[i][1]]>f[j])
                f[j]=f[j-v[i]-v[s[i][1]]]+w[i]+w[s[i][1]];
            if(s[i][0]==2&&f[j-v[i]-v[s[i][2]]]+w[i]+w[s[i][2]]>f[j])
                f[j]=f[j-v[i]-v[s[i][2]]]+w[i]+w[s[i][2]];
            if(s[i][0]==2&&f[j-v[i]-v[s[i][1]]-v[s[i][2]]]+w[i]+w[s[i][1]]+w[s[i][2]]>f[j])
                f[j]=f[j-v[i]-v[s[i][1]]-v[s[i][2]]]+w[i]+w[s[i][1]]+w[s[i][2]];
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++)
        if(f[i]>ans)ans=f[i];
    printf("%d\n",ans);
    return 0;
}

by Shik__Utau @ 2019-09-02 21:18:12

90pt了

#include<bits/stdc++.h>
using namespace std;
int n,m,w[65],v[65],s[65][3]={0},f[32005];
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d%d%d",&v[i],&w[i],&x);
        w[i]*=v[i];
        if(x)s[x][++s[x][0]]=i,s[i][0]=3;
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++){
        if(s[i][0]==3)continue;
        for(int j=m;j>=v[i];j--){
            int minn=f[j];
            if(f[j-v[i]]+w[i]>f[j])f[j]=f[j-v[i]]+w[i];
            if(s[i][0]==1&&j-v[i]-v[s[i][1]]>=0&&f[j-v[i]-v[s[i][1]]]+w[i]+w[s[i][1]]>f[j])
                f[j]=f[j-v[i]-v[s[i][1]]]+w[i]+w[s[i][1]];
            if(s[i][0]==2&&j-v[i]-v[s[i][2]]>=0&&f[j-v[i]-v[s[i][2]]]+w[i]+w[s[i][2]]>f[j])
                f[j]=f[j-v[i]-v[s[i][2]]]+w[i]+w[s[i][2]];
            if(s[i][0]==2&&j-v[i]-v[s[i][1]]-v[s[i][2]]>=0&&f[j-v[i]-v[s[i][1]]-v[s[i][2]]]+w[i]+w[s[i][1]]+w[s[i][2]]>f[j])
                f[j]=f[j-v[i]-v[s[i][1]]-v[s[i][2]]]+w[i]+w[s[i][1]]+w[s[i][2]];
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++)
        if(f[i]>ans)ans=f[i];
    printf("%d\n",ans);
    return 0;
}

by hanyufei @ 2019-09-02 21:32:20

pragma GCC optimize(1)

pragma GCC optimize(2)

pragma GCC optimize(3)

include<bits/stdc++.h>

using namespace std; inline int read() { int x=0,h=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') h=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x10+(ch^48);ch=getchar();} return xh; } const int N=50001; int n,m,f[N],w[N][3],v[N][3],used[N]; int main() { n=read(),m=read(); for(register int i=1;i<=m;++i) { int a=read(),b=read(),c=read(); if(c==0) w[i][0]=a,v[i][0]=ab; else used[c]++,w[c][used[c]]=a,v[c][used[c]]=ab; } for(register int i=1;i<=m;++i) for(register int j=n;w[i][0]!=0&&j>=w[i][0];--j) { if(j>=w[i][0]) f[j]=max(f[j],f[j-w[i][0]]+v[i][0]); if(j>=w[i][0]+w[i][1]) f[j]=max(f[j],f[j-w[i][0]-w[i][1]]+v[i][0]+v[i][1]); if(j>=w[i][0]+w[i][1]+w[i][2]) f[j]=max(f[j],f[j-w[i][0]-w[i][1]-w[i][2]]+v[i][0]+v[i][1]+v[i][2]); } printf("%d\n",f[n]); return 0; }

by hanyufei @ 2019-09-02 21:32:58

hahahaha---------

by KellyFrog @ 2019-09-02 21:46:57

希望实现更丰富的展示？使用markdown

by JeffWang2019 @ 2019-09-18 21:51:15

@hanyufei 这代码谁能看下去