AcWing 487. 金明的预算方案
原题链接
中等
作者:
wangyj
,
2021-01-16 19:54:53
,
所有人可见
,
阅读 551
#include<iostream>
#include<vector>
using namespace std;
struct good{
int w,t;
};
vector<good>v[61];
int n,m,a,b,c,f[32001];
int max(int x,int y){return x>y?x:y;}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
int temp=v[c].size();
if(!c)v[i].push_back({a,a*b});
else for(int k=0;k<temp;k++)v[c].push_back({a+v[c][k].w,a*b+v[c][k].t});
}
for(int i=1;i<=m;i++)for(int j=n;j>=0;j--)for(int k=0;k<v[i].size();k++){
good now=v[i][k];
if(j>=now.w)f[j]=max(f[j],f[j-now.w]+now.t);
}
printf("%d",f[n]);
return 0;
}
做的挺快的
谢谢你呀🌹🌹🌹