【每日一题】美味佳肴

题意

$n$ 件食材（每种食材的数量可以视为无限），小明连续工作 $T$ 时间。每道菜肴的制作需要特定的一种食材以及一段时间，但是食材一旦放久就不新鲜了，菜的美味值会降低。第 $i$ 道菜肴有三个属性 $ai$ ， $bi$ ， $ci$ ， $ai$ 是该菜肴的美味值， $bi$ 是该菜肴所选食材不新鲜的速率，如果在第t时刻完成第i道菜则美味值为： $ai-t*bi$ ，完成这道菜需要 $ci$ 的时间。求在这 $T$ 时间内能做出菜肴使得总美味值的最大值。

solution

首先需要贪心确定顺序，考虑只有两道菜，可以得到： $a_i−b_i∗c_i+(a_j−b_j∗(c_i+c_j))>=a_j−b_j∗c_j+(a_i−b_i∗(c_i+c_j))$ ，化简后得到： $b_i∗c_i>=b_j∗c_i$ 。排序后背包即可（需要降维）。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3ffffffffffff;
const int N = 2e5 + 5;

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

ll res = -INF, s[N], dp[N];

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] = -INF;
  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++) res = max(res, dp[i]);
  cout << res << '\n';
  return 0;
}