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
前排同问