Mamba_ever_out @ 2020-02-09 11:29:54
#include<bits/stdc++.h>
using namespace std;
int a[71][33001];
int b[71];
int v[71];
int p[71];
int wz[71][71];
int gs[71];
int dp[33001];
int main(){
int n,m;
cin>>n>>m;
int num = 1;
for(int i=1;i<=m;i++){
int q;
scanf("%d%d%d",&v[i],&p[i],&q);
if(q==0){
b[num] = i;
num++;
}
else{
wz[q][gs[q]+1] = i;
gs[q] ++;
}
}
num -- ;
for(int i=1;i<=num;i++){
for(int j=n-v[b[i]];j>=1;j--){
for(int k=1;k<=gs[b[i]];k++){
if(j-v[wz[b[i]][k]]>=0)
dp[j] = max(dp[j],dp[j-v[wz[b[i]][k]]]+p[wz[b[i]][k]]*v[wz[b[i]][k]]);
else
;
}
}
for(int j=0;j<=n-v[b[i]];j++){
a[i][j+v[b[i]]] = dp[j] + p[b[i]]*v[b[i]];
dp[j]=0;
}
}
for(int i = 1;i<=num;i++){
for(int k=n;k>=1;k--){
for(int m=n;m>=1;m--){
if(k-m>=0)
dp[k] = max(dp[k],dp[k-m]+a[i][m]);
else
;
}
}
}
cout<<dp[n];
return 0;
}by tangrunxi @ 2020-02-09 11:33:10
int a[71][33001];你不觉得要开 long long 吗
by tangrunxi @ 2020-02-09 11:33:16
@zhangthreewind
by Mamba_ever_out @ 2020-02-09 11:37:34
@tangrunxi 可是他说输出小于200000
by tangrunxi @ 2020-02-09 11:39:35
@zhangthreewind 输出的是这个
cout<<dp[n];我说a数组开小了。
by Mamba_ever_out @ 2020-02-09 11:43:45
@tangrunxi 我的a[i][j]表示的是第i组物品（每组就是一个主产品和各种附属产品在j个金钱的情况下能获得的最高价值）数量为60 金钱最多为32000，应该不会超的啊
by Mamba_ever_out @ 2020-02-09 13:31:23
上面01背包位置写反现在改正为
for(int k=1;k<=gs[b[i]];k++){ //里面就相当于看成 01背包 ，在这其中已经算(默认已经算进主产品)
for(int j=n-v[b[i]];j>=1;j--){ // 购买了主产品，所以对金币计算会有所改动
if(j-v[wz[b[i]][k]]>=0)
dp[j] = max(dp[j],dp[j-v[wz[b[i]][k]]]+p[wz[b[i]][k]]*v[wz[b[i]][k]]);
}
}