牛客网【每日一题】4月28日题目精讲 美味菜肴

链接：

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld

题目描述

小明是个大厨，早上起来他开始一天的工作。他所在的餐厅每天早上都会买好n件食材（每种食材的数量可以视为无限），小明从到达餐厅开始就连续工作T时间。每道菜肴的制作需要特定的一种食材以及一段时间，但是食材一旦放久就不新鲜了，菜的美味值会降低。第i道菜肴有三个属性ai，bi，ci，ai是该菜肴的美味值，bi是该菜肴所选食材不新鲜的速率，如果在第t时刻完成第i道菜则美味值为：ai-t*bi，完成这道菜需要ci的时间。小明希望在这T时间内能做出菜肴使得总美味值最大，所以小明求助于你。

输入描述:

第1行输入三个整数n，m，T，分别代表食材种类，菜肴种类和工作时间。 第2行输入n个整数bi，代表第i个食材不新鲜的速率。
第3-n+2行，每行输入三个整数j，ai，ci，分别代表第i道菜肴需要的食材编号，菜肴的美味值，完成时间。
数据保证：0<n,m≤50，0<j≤n，其他值均<106，美味值必须通过完整做出菜肴得到，数据保证在规定时间内至少能完整做出1道菜肴。

输出描述:

输出一行，一个整数，表示最大总美味值。

示例1
输入
复制

1 1 74 2 1 502 47

输出
复制

408

示例2
输入
复制

2 2 10 2 1 1 100 8 2 50 3

输出
复制

84

备注:
最大总美味值可能为负。

题解：

看完题第一反应是比性价比（最近刚做了一个题），就是制造出一个评比标准，然后排序，进行美味值计算
两个菜肴x和y先后制作看看美味值
先x后y：a[x]−(sum+t[x])∗b[x]+a[y]−(sum+t[x]+t[y])∗b[y]（1）
先y后x：a[y]−(sum+t[y])∗b[y]+a[x]−(sum+t[x]+t[y])∗b[x]（2）
sum是之前所做的菜所用的时间
我们要知道哪个顺序做最佳，两者比较，假如说先x后y最佳，式子1>式子2，经过化简可以得到tx/bx<ty/by，除法多不好算，改成乘法
t_x * b_y< t_y* b_x
然后我们可以用dp来做，01背包，dp[i]表示各个时间t完美味值情况
我用的结构体，edge[]
a美味值,b不新鲜速率,c时间,j顺序

dp[j]=max(dp[j],dp[j-edge[i].c]+edge[i].a-j*edge[edge[i].j].b);

dp[j-edge[i].c]+edge[i].a-jedge[edge[i].j].b中
第一个dp表示在做这个菜之前的时间内所得到的美味值
edge[i].a表示食材起初的美味值
jedge[edge[i].j].b表示当前菜所要消耗的新鲜值
后两者相减为做这个菜所得到的美味值

#include<bits/stdc++.h> typedef long long ll; using namespace std; const int inf=-1e9-2; const int maxn=2e5+8; ll sum=inf;//美味值可能是负值 int n,m,t; ll dp[maxn]; struct node{ll j,a,b,c; }edge[maxn]; //bool max(int x,int y) //{ // return x<y; //} bool cmp(node x,node y) {return x.c*edge[y.j].b<y.c*edge[x.j].b; } int main() {scanf("%lld%lld%lld",&n,&m,&t);for(int i=1;i<=n;i++)scanf("%lld",&edge[i].b);for(int i=1;i<=m;i++)scanf("%lld%lld%lld",&edge[i].j,&edge[i].a,&edge[i].c);sort(edge+1,edge+1+m,cmp); // // for(int i=1;i<=m;i++) // { // cout<<edge[i].j<<" "<<edge[i].a<<" "<<edge[i].b<<" "<<edge[i].c<<endl; // }for(int i=1;i<=t;i++)dp[i]=inf;//dp赋最小值 for(int i=1;i<=m;i++)for(int j=t;j>=edge[i].c;j--){ll w= dp[j-edge[i].c]+ edge[i].a - j * edge[i].b; // printf("%lld %lld %lld\n ",dp[j-edge[i].c],edge[i].a,j * edge[i].b);dp[j]=max( dp[j] , dp[j-edge[i].c]+edge[i].a-j * edge[i].b); // printf("w=%lld,dp[%d]=%lld\n",w,j,dp[j]);} for(int i=1;i<=t;i++)sum=max(sum,dp[i]);cout<<sum<<endl;return 0; } /* 2 2 10 2 1 1 100 8 2 50 3 */ /* 100 2 8 50 1 3 */

总结

以上是生活随笔为你收集整理的牛客网【每日一题】4月28日题目精讲 美味菜肴的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。