AcWing 487. 金明的预算方案(码力不够,暴力来凑)
原题链接
中等
作者:
ny_tian720
,
2024-04-05 20:43:20
,
所有人可见
,
阅读 2
大聪明做法,好实现,适合菜鸡(比如我)
(码力不够,暴力来凑) $O(4nm)$
思路:逐个暴力捆绑(四种情况),最后直接转换成分组背包模板
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll f[600010],n,m,v[300][5],w[300][5],aa,bb,cc;
ll xx[70][4][2],idx;
ll s[70],x[70][5];
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>aa>>bb>>cc;
if(cc==0){
xx[i][0][0]=aa;
xx[i][0][1]=aa*bb;
}
else{
if(!xx[cc][1][0]){
xx[cc][1][0]=aa;
xx[cc][1][1]=aa*bb;
}
else{
xx[cc][2][0]=aa;
xx[cc][2][1]=aa*bb;
}
}
}
for(int i=1;i<=m;i++){
if(!xx[i][0][0]) continue;
if(!xx[i][1][0]){
v[i][++s[i]]=xx[i][0][0];
w[i][s[i]]=xx[i][0][1];
}
else if(!xx[i][2][0]){
v[i][++s[i]]=xx[i][0][0];
w[i][s[i]]=xx[i][0][1];
v[i][++s[i]]=xx[i][0][0]+xx[i][1][0];
w[i][s[i]]=xx[i][0][1]+xx[i][1][1];
}
else{
v[i][++s[i]]=xx[i][0][0];
w[i][s[i]]=xx[i][0][1];
v[i][++s[i]]=xx[i][0][0]+xx[i][1][0];
w[i][s[i]]=xx[i][0][1]+xx[i][1][1];
v[i][++s[i]]=xx[i][0][0]+xx[i][2][0];
w[i][s[i]]=xx[i][0][1]+xx[i][2][1];
v[i][++s[i]]=xx[i][0][0]+xx[i][1][0]+xx[i][2][0];
w[i][s[i]]=xx[i][0][1]+xx[i][1][1]+xx[i][2][1];
}
}
for(int i=1;i<=m;i++){
if(!xx[i][0][0]) continue;
for(int j=n;j>=0;j--){
for(int k=1;k<=s[i];k++){
if(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[n];
return 0;
}