调了好久,求助dalao

P1064 [NOIP2006 提高组] 金明的预算方案

EEchoyukii @ 2019-11-07 20:48:13

样例没过,求dalao修改,谢谢

#include<iostream>
#include<cstdio>
using namespace std;
inline int read(){
    register int x=0,v=1,ch=getchar();
    while(!isdigit(ch)){if(ch=='-')v=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
    return x*v;
}
const int MAX=65,N=32005;
int W,n,u[MAX],f[N];
int w[MAX],v[MAX],ch[MAX][10],cnt[MAX],c1,c2;
int main(){
    W=read(),n=read();
    for(register int i=1;i<=n;++i){
        w[i]=read();v[i]=w[i]*read();
        u[i]=read();
        if(u[i]!=0)ch[u[i]][++cnt[u[i]]]=i; 
    }
    for(register int i=1;i<=n;++i){
        if(u[i]==0){//是主件   
            c1=ch[i][1];c2=ch[i][2];
            for(register int j=W;j>=w[i];--j)f[j]=max(f[j],f[j-w[i]]+v[i]);
            //只选主件 
            for(register int j=W;j>=w[i]+w[c1];--j)f[j]=max(f[j],f[j-w[i]-w[c1]]+v[i]+v[c1]);
            //主件+附件1 
            if(cnt[i]==2){
                for(register int j=W;j>=w[i]+w[c2];--j)f[j]=max(f[j],f[j-w[i]-w[c2]]+v[i]+v[c2]);
                //主件+附件2 
                for(register int j=W;j>=w[i]+w[c1]+w[c2];--j)f[j]=max(f[j],f[j-w[i]-w[c1-w[c2]]]+v[i]+v[c1]+v[c2]);
                //主件+附件1+附件2 
            }
        }
    }
    printf("%d\n",f[W]);
    return 0;
}

by 蒟蒻本人 @ 2019-11-07 20:55:03

 if(cnt[i]>=1)
            for(register int j=W;j>=w[i]+w[c1];--j)f[j]=max(f[j],f[j-w[i]-w[c1]]+v[i]+v[c1]);
            //主件+附件1 

by 蒟蒻本人 @ 2019-11-07 20:55:07

@AK永动机


by EEchoyukii @ 2019-11-07 20:57:40

@蒟蒻本人 谢谢dalao


|