美味菜肴

题意:在给定的时间内,选择做几种菜肴,然后让美味度最大
题解:第一眼01背包,然后再看,额,比01背包还多了个条件,就是,在不同的时间内做出来的菜,美味度会有变化,答案还可能负的(负的还能吃吗???,弥天大雾)
所以就是先进行贪心,把给定的数列处理成可以01背包的数列
既然是贪心,那么肯定 ,所以假设有 两种菜,那么选个菜就是 和两式相减,求贪心,化简得到 ,然后就可以进行贪心 了.
下来01背包拉进去
时间复杂度:

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

struct Node {
  long long a, b, c;
} q[N];

long long s[N], dp[N],ans=-99999999;

bool cmp(Node x, Node y) { return x.c * s[y.a] < y.c * s[x.a]; }

int main() {
  int n, m, t;
  cin >> n >> m >> t;
  for (int i = 1; i <= n; i++) cin >> s[i];
  for (int i = 1; i <= m; i++) cin >> q[i].a >> q[i].b >> q[i].c;
  sort(q + 1, q + m + 1, cmp);
  for (int i = 1; i <= t; i++) dp[i] = -999999999;
  for (int i = 1; i <= m; i++)
    for (int j = t; j >= q[i].c; j--)
      dp[j] = max(dp[j], dp[j - q[i].c] + q[i].b - j * s[q[i].a]);
  for (int i = 1; i <= t; i++) ans= max(ans, dp[i]);
cout<<ans;
  return 0;
}