洛谷 1417 烹饪方案

2023-11-09 22:50

文章标签 方案洛谷烹饪 1417

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

http://dev.luogu.org:3308/problem/show?pid=1417
月考跪碎了膝盖，回到家赶紧敲个题压压惊。。。
贪心+DP
看了题解神犇的思路：

现在考虑相邻的两个物品x,y。假设现在已经耗费p的时间，那么分别列出先做x,y的代价：
a[x]-(p+c[x])*b[x]+a[y]-(p+c[x]+c[y])*by
a[y]-(p+c[y])*b[y]+a[x]-(p+c[y]+c[x])*bx
对这两个式子化简，得到①＞②的条件是c[x]*b[y] < c[y]*b[x]

所以按x.c*y.b < x.b*y.c的顺序排序，然后01背包，状态转移方程是：
for(j=T;j>=ar[i].c;j–)
f[j]=max{f[j-ar[i].c]+ar[i].a-j*ar[i].b}
注意要用long long不然会RE。。。还要记得f[0]=0。。。因为这些细节挂了好多次。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{long long a,b,c;
}ar[100];
long long f[100010],n,T,ans;
bool cmp(node x,node y)
{return x.c*y.b<x.b*y.c;
}
int main()
{memset(f,255,sizeof(f));scanf("%lld%lld",&T,&n);for(int i=1;i<=n;i++)scanf("%lld",&ar[i].a);for(int i=1;i<=n;i++)scanf("%lld",&ar[i].b);for(int i=1;i<=n;i++)scanf("%lld",&ar[i].c);sort(ar+1,ar+1+n,cmp);f[0]=0;for(int i=1;i<=n;i++){for(int j=T;j>=ar[i].c;j--){if(f[j-ar[i].c]!=-1){f[j]=max(f[j],f[j-ar[i].c]+ar[i].a-j*ar[i].b);}}}for(int i=0;i<=T;i++)ans=max(ans,f[i]);printf("%lld",ans);return 0;
}