美食大赛的题解
2023-12-13 06:14:07
目录
原题描述:
题目描述:
美食城正在举行一年一度的美食大赛。小 Q 是其中一位参赛选手,他有 个食材,第 个食材做成菜所需要的时间为 。由于新鲜度的问题,如果第 个食材在时间时才被做成菜,那么这道菜的美味度为 ,其中 和 是给定的参数。大赛时间紧张,总共只有 的时间。小 Q 想在 T 时间内做出的菜的美味度之和尽可能大,你能帮帮他吗?
输入格式:
第一行包含两个整数 和 。
接下来三行,每行 个数,分别表示 ~,~,~。
输出格式:
输出一行一个数,表示答案。
样例输入:
74 1
502
2
47
样例输出:
408
数据规模:?
,其余所有数都不超过。
题目大意:
给你三个数组,代表n个食物,让你选择先后顺序,然后算出最优值。
主要思路:
这个题目看上去就是01背包问题,但是这不完全是01背包问题,因为它和先后顺序有关:
设有两个食物,x,y,已经耗了p的时间。
如果先煮x,再煮y。则价值为:? 设为①
如果先煮y,再煮x。则价值为:?设为②
如果想让①>②,那化简不等式:就是
所以我们根据这个排个序,再01背包就好了
注:
我们可以边01背包,边记录答案,这样就不用枚举了。
代码:
#include<bits/stdc++.h>
using namespace std;
struct m{
long long a,b,c;//每种食物的属性
}x[100010];
int n,t;
long long dp[100010];
long long ans;
bool cmp(m a,m b)
{
return a.c*b.b<a.b*b.c;//排序
}
int main()
{
// freopen("sample (44).in","r",stdin);
cin>>t>>n;
for(int i=1;i<=n;i++)
{
cin>>x[i].a;
}
for(int i=1;i<=n;i++)
{
cin>>x[i].b;
}
for(int i=1;i<=n;i++)
{
cin>>x[i].c;
}
sort(x+1,x+1+n,cmp);
for(int i=1;i<=n;i++)
{
for(int j=t;j>=x[i].c;j--)
{
dp[j] = max(dp[j],dp[j-x[i].c]+x[i].a-j*x[i].b);//经典的01背包转移方程
ans = max(ans,dp[j]);//边做边记录
}
}
cout<<ans;
return 0;
}
文章来源:https://blog.csdn.net/a613322/article/details/134892602
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!