洛谷 1417 烹调方案#01背包,贪心#

本文主要是介绍洛谷 1417 烹调方案#01背包,贪心#，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

如果在$t$时刻完成第$i$样食材则得到$ai-t\ast bi$的美味指数，用第i件食材做饭要花去$ci$的时间，求最大美味指数。

---

分析

如果没有$b[i]$那么就是赤裸裸的01背包，但是这道题先要判断顺序。
01背包：$f[j]=\max (f[j],f[j-w[i]]+c[i])$
所以要用一种贪心的思想
已经耗费$t$时间，先做$x，y$的代价
$先做x：a[x]-(t+c[x])\ast b[x]+a[y]-(t+c[x]+c[y])\ast b[y]$
$先做y：a[y]-(t+c[y])\ast b[y]+a[x]-(t+c[y]+c[x])\ast b[x]$
化简发现贪心与$a$无关，只需要$c[x]\ast b[y]$和$c[y]\ast b[x]$

---

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#define int64 long long
using namespace std;
struct menu{int64 a,b,c;}cook[51]; int64 f[100001],ans,n,m; 
bool cmp(menu x,menu y){return x.c*y.b<y.c*x.b;}
int64 in(){int64 ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
int main(){m=in(); n=in();for (int i=1;i<=n;i++) cook[i].a=in();for (int i=1;i<=n;i++) cook[i].b=in();for (int i=1;i<=n;i++) cook[i].c=in();stable_sort(cook+1,cook+1+n,cmp);for (int i=1;i<=n;i++)for (int j=m;j>=cook[i].c;j--)f[j]=max(f[j],f[j-cook[i].c]+cook[i].a-cook[i].b*j);for (int i=1;i<=m;i++) ans=max(ans,f[i]);printf("%lld",ans);return 0;
}

这篇关于洛谷 1417 烹调方案#01背包,贪心#的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---