WA了四个点,求助

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

Grace25 @ 2020-11-01 12:46:28

X﹏X,我真的太弱了

#include<iostream>

#include<algorithm> 

#include<cstring>

using namespace std;

long long n,s,m=1,dp[32010],dp_f[32010];

struct thing{

    int v,w,h;

}main_item[10010],annex_item[1010][1010];

int main(){

    int v,w,h;

    cin >> s >> n;

    for(int i=1;i<=n;i++){

        cin >> w >> v >> h;

        if (!h){//是主件 

            main_item[0].h++;//件数加一 

            main_item[main_item[0].h].v = v*w//储存 

            main_item[main_item[0].h].w = w;

        }else{//是附件 

            annex_item[h][0].h++;//件数加一 

            annex_item[h][annex_item[h][0].h].v = v*w;//储存 

            annex_item[h][annex_item[h][0].h].w = w;

        }

    }   

    for(int i=1;i<=main_item[0].h;i++){ 

        memcpy(dp_f,dp,sizeof(dp));        

        for(int j=1;j<=annex_item[i][0].h;j++){//对附件进行0-1背包

            w=annex_item[i][j].w; 

            v=annex_item[i][j].v;           

            for(int x=s;x>=w;x--){               

                dp_f[x]=max(dp_f[x],dp_f[x-w]+v);

            }

        }
       w=main_item[i].w; 

        v=main_item[i].v;

        for(int j=s;j>=w;j--){

            dp[j]=max(dp[j],dp_f[j-w]+v);

        }

    }
    cout << dp[s];
    return 0;
}

|