01背包、排序
很容易看出来这是一个01背包,但是因为价值跟所完成的时间有关(即跟选取顺序有关),所以不能按照顺序直接背包,要先排序。
考虑第i个和第j个两个菜,假设先完成第i个菜的价值更大,则有
化简后得到
按照上式排序后,01背包即可。
注意答案可能为负,dp数组除dp[0]外应赋为无穷小
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll dp[1<<20]; ll b[1<<20]; struct node{ ll b,a,c; }a[1<<20]; int main(){ int n,m,T;cin>>n>>m>>T; for(int i=1;i<=n;i++) cin>>b[i]; for(int i=1;i<=m;i++) cin>>a[i].b>>a[i].a>>a[i].c,a[i].b=b[a[i].b]; sort(a+1,a+1+m,[](node x,node y){ return x.b*y.c>x.c*y.b; }); for(int i=1;i<=T;i++) dp[i]=-1e18; for(int i=1;i<=m;i++){ for(int l=T;l>=a[i].c;l--){ dp[l]=max(dp[l],dp[l-a[i].c]+a[i].a-l*a[i].b); } } ll ans=-1e18; for(int i=1;i<=T;i++) ans=max(ans,dp[i]); cout<<ans<<endl; return 0; }