每日一题 4.28 美味菜肴

这是一道带点变化的01背包题
首先对要做的 x y 两道菜怎么确定他们的先后关系？
先做x后做y的美味值和为：a[x]-(\sum +t[x])b[x] + a[y] - (\sum + t[x] + t[y]) * b[y]a[x]−(\sum+t[x])∗b[x]+a[y]−(\sum+t[x]+t[y])∗b[y]
先做y后做x的美味值和为：a[y]-(\sum +t[y])b[y] + a[x] - (\sum + t[x] + t[y]) * b[x]a[y]−(\sum+t[y])∗b[y]+a[x]−(\sum+t[x]+t[y])∗b[x]
（\sum是做前面所有菜的时间和）
比较大小就可知道 排序规则是 c[x]b[y[j]]<c[y]b[x[j]]
然后就是考虑第i道菜做不做
dp[j] = max(dp[j], dp[j - k[i].c] + k[i].a - b[k[i].j] * j)
ps:注意至少要做一个菜

#include <bits/stdc++.h>
#define ll long long
int const N=1e6+5;
using namespace std;
ll n,m,t,b[N],dp[N];
struct T{
  int a,c,j;
}k[N];
bool cmp(T x,T y){return x.c*b[y.j]<y.c*b[x.j];}
int main()
{
   cin>>n>>m>>t;
   for(int i=1;i<=n;++i)cin>>b[i];
   for(int i=1;i<=m;++i)
   {
       cin>>k[i].j>>k[i].a>>k[i].c;
   }
   sort(k+1,k+1+m,cmp);
   memset(dp, -0x3f, sizeof(dp));///避免一个菜也不做
   dp[0] = 0;
   ll  ans = -1e18;
   for(int i = 1; i <= m; i++) {
    for(int j = t; j >= k[i].c; j--) {
      dp[j] = max(dp[j], dp[j - k[i].c] + k[i].a - b[k[i].j] * j);///这个菜做还是不做
      ans = max(ans, dp[j]);
    }
  }
   cout<<ans<<endl;
    return 0;
}