【每日一题】美味佳肴 4.27
美味菜肴
https://ac.nowcoder.com/acm/problem/14704
01背包问题
但并不是简单的01背包问题，因为与选取的顺序有关，观察公式A[i]-t*B[i]，对任意两道菜先选哪道菜结果肯定最大呢?
化简一下公式就可以知道，只有末尾一项不一样，那么按末尾那项降序排列即可
然后就是01背包问题了，重量是c，价值是a[i]-b[i]*t(t是做完这道菜的时间)，背包容量是T，即可得到答案了
最后记得开long long
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e6+7;
const int inf = 0x3f3f3f3f;
ll dp[maxn],f[55];
struct node{
ll a,b,c;
bool operator < (const node& x)const
{
return c*x.b<x.c*b;
}
}p[55];
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int n,m,T;
cin>>n>>m>>T;
for(int i=1;i<=n;i++) cin>>f[i];
for(int i=1;i<=m;i++)
{
cin>>p[i].b>>p[i].a>>p[i].c;
p[i].b = f[p[i].b];
}
sort(p+1,p+1+m);
memset(dp,-inf,sizeof(dp));dp[0] = 0;
//01背包
for(int i=1;i<=m;i++)
for(int j=T;j>=p[i].c;j--)
{
dp[j] = max(dp[j],dp[j-p[i].c]+p[i].a-j*p[i].b);
}
ll ans = -inf;
for(int i=1;i<=T;i++) ans = max(ans,dp[i]);
cout<<ans;
return 0;
}
