1064高端解法高端分数

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

ganyiming @ 2021-07-22 10:35:11

用先打包的写法,只有20点不知道除了什么问题,求大佬指点

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int mx=150010;
int f[mx],v[mx],w[mx],cnt;//价格,价值
int n,m;//总钱数,物品个数
int v1[mx],w1[mx],p1[mx],son[mx];
int main(){
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> v1[i] >> w1[i] >> p1[i];//价格 重要度 主附件
    }
    for(int i=1;i<=m;i++){
        if(p1[i]==0){//只有一个主件
            v[++cnt]=v1[i];
            w[cnt]=v1[i]*w1[i];
        }
        else {
            if(son[p1[i]]!=0){
                int x=p1[i],s=son[p1[i]];
                v[++cnt]=v1[i]+v1[x];
                w[cnt]=v1[i]*w1[i]+v1[x]*w1[x];//主件+第二个附
                v[++cnt]=v1[i]+v1[x]+v1[s];
                w[cnt]=v1[i]*w1[i]+v1[x]*w1[x]+v1[s]*w1[s];//主件+附2+附1
            }
            if(son[p1[i]]==0){
                son[p1[i]]=i;
                int x=p1[i];
                v[++cnt]=v1[i]+v1[x];
                w[cnt]=v1[i]*w1[i]+v1[x]*w1[x];//主件+附1
            }
        }
    }
    // for(int i=1;i<=cnt;i++) cout<<v[i]<<" "<<w[i]<<endl; 
    for(int i=1;i<=cnt;i++){

        for(int j=n;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[n]<<endl;
    return 0;
}

by AdGats @ 2021-07-24 10:37:05

同问诶


by 鲁笑含 @ 2021-09-20 16:44:11

前排同问


|