题解
2023-08-20 10:17:33
发布于:广东
4阅读
0回复
0点赞
#include <bits/stdc++.h>
#define maxn 32010
using namespace std;
int main_item_w[maxn],main_item_c[maxn],aiw[maxn][3], aic[maxn][3],dp[maxn];
int main(){
int n,m,v,p,q;
cin >> n >> m;
for (int i=1;i<=m;i++){
cin >> v >> p >> q;
if (!q){
main_item_w[i] = v;
main_item_c[i] = v * p;
}
else{
aiw[q][0]++;
aiw[q][aiw[q][0]] = v;
aic[q][aiw[q][0]] = v * p;
}
}
for (int i=1;i<=m;i++)
for (int j=n;main_item_w[i]!=0 && j>=main_item_w[i];j--){
dp[j] = max(dp[j],dp[j-main_item_w[i]]+main_item_c[i]);
if (j >= main_item_w[i] + aiw[i][1])
dp[j] = max(dp[j],dp[ j - main_item_w[i] - aiw[i][1] ] + main_item_c[i] + aic[i][1]);
if (j >= main_item_w[i] + aiw[i][2])
dp[j] = max(dp[j],dp[ j - main_item_w[i] - aiw[i][2] ] + main_item_c[i] + aic[i][2]);
if (j >= main_item_w[i] + aiw[i][1] + aiw[i][2])
dp[j] = max(dp[j],dp[ j - main_item_w[i] - aiw[i][1] - aiw[i][2] ] + main_item_c[i] + aic[i][1] + aic[i][2]);
}
cout << dp[n] << endl;
return 0;
}
这里空空如也
有帮助,赞一个