60分求助,初中刚学

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

lsz0205 @ 2022-11-14 20:08:26

#include<iostream> 
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

// 首先为每个主件建立一个组
// 其次,把对应的附件添加进组 

vector<int> v[70];
vector<int> w[70];

vector<int> fv;
vector<int> fw;
vector<int> od;

int n,m;
int f[70][32000+10];

vector<int> nv[70];
vector<int> nw[70];

int main(){

    for(int i=0;i<70;i++) v[i].push_back(0),w[i].push_back(0);

    cin>>m>>n;
    int idx=1;
    for(int i=1;i<=n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(z==0){
            v[idx].push_back(x);
            w[idx].push_back(x*y);
            idx++;
        }else{ // 附件 
            fv.push_back(x);
            fw.push_back(x*y);
            od.push_back(z);
        }
    }

    // 把各个附件添加进组
    for(int i=0;i<od.size();i++){
        int no=od[i];
        v[no].push_back(fv[i]);
        w[no].push_back(fw[i]);
    }

    // 计算真正的组内的元素的v和w

    for(int i=1;i<=idx-1;i++){ // 一共有idx-1个组 
        nv[i].push_back(0);
        nw[i].push_back(0);
        if(v[i].size()==2){ // 只有主件 
            nv[i].push_back(v[i][1]);
            nw[i].push_back(w[i][1]);
        }else if(v[i].size()==3){ // 一个主件一个附件 
            nv[i].push_back(v[i][1]);
            nw[i].push_back(w[i][1]);

            nv[i].push_back(v[i][1]+v[i][2]);
            nw[i].push_back(w[i][1]+w[i][2]);                   
        }else{ // 一个主件两个附件 
            nv[i].push_back(v[i][1]);
            nw[i].push_back(w[i][1]);

            nv[i].push_back(v[i][1]+v[i][2]);
            nw[i].push_back(w[i][1]+w[i][2]);

            nv[i].push_back(v[i][1]+v[i][3]);
            nw[i].push_back(w[i][1]+w[i][3]);

            nv[i].push_back(v[i][1]+v[i][2]+v[i][3]);
            nw[i].push_back(w[i][1]+w[i][2]+w[i][3]);
        } 
    } 

    for(int i=1;i<=idx-1;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=f[i-1][j];
            for(int k=1;k<nv[i].size();k++){
                if(j>=nv[i][k]) f[i][j]=max(f[i][j],f[i-1][j-nv[i][k]]+nw[i][k]);
            }
        }
    }
    cout<<f[idx-1][m]<<endl;

    return 0;
}

by ZJH123767 @ 2022-11-16 07:55:33

看起来挺对


by PCCP @ 2022-11-17 20:40:07

可以看看我在本题发的我的帖子,对你会很有启发


by lsz0205 @ 2022-11-19 19:20:22

@PCCP 十分感谢


|