【题解】免费菜肴

这题是一个 01 背包的形式，唯一可能的解法是动态规划。

但在本题未经处理的情况下，动态规划是不能使用的。因为原图上的转移不是有向无环图，带来了后效性，使得动态规划出错。

于是我们需要安排一种转移顺序，使得原图的转移变成 DAG，从而应用动态规划解决问题。

结论是，一定存在一种最优方案 ，使得对于任意 ，都有 。

证明如下：若不满足该条件，则必然存在一个位置 ，满足 。

我们把 和 两道菜肴拎出来，单独计算它们对答案的贡献。

设这种方案中开始制作 的时间为 。

若按照 的顺序制作菜肴，则对答案的贡献为 。

如果我们交换 和 的顺序，变成按照 的顺序制作菜肴，则对答案的贡献为 。

作差法比较两贡献的大小关系，可以得到

由于 ，则 。也就是说，如果交换了 和 的顺序，可以使得答案变大，故而原方案不是最优方案，证毕。

于是我们可以将所有菜肴按照 从大到小排序，然后再从前往后做一遍 01 背包即可。

时间复杂度 。

代码：

#include <algorithm>
#include <cstdio>
#include <cstring>

const int MaxN = 50, MaxM = 50, MaxT = 1000000;
const long long NeInf = 0x8080808080808080;

int N, M, T;
int B[MaxN + 5];
int J[MaxM + 5], A[MaxM + 5], C[MaxM + 5];
int Lnk[MaxM + 5];
long long F[MaxT + 5];

void init() {
  scanf("%d %d %d", &N, &M, &T);
  for (int i = 1; i <= N; ++i) scanf("%d", &B[i]);
  for (int i = 1; i <= M; ++i) scanf("%d %d %d", &J[i], &A[i], &C[i]);
}

inline bool cmp(int x, int y) {
  return 1.0 * B[J[x]] / C[x] > 1.0 * B[J[y]] / C[y];
}

void solve() {
  for (int i = 1; i <= M; ++i) Lnk[i] = i;
  std::sort(Lnk + 1, Lnk + 1 + M, cmp);
  memset(F, 0x80, sizeof F);
  F[0] = 0;
  for (int I = 1; I <= M; ++I) {
    int i = Lnk[I];
    for (int j = T; j >= C[i]; --j)
      F[j] = std::max(F[j], F[j - C[i]] + A[i] - 1LL * B[J[i]] * j);
  }
  long long ans = NeInf;
  for (int i = 1; i <= T; ++i) ans = std::max(ans, F[i]);
  printf("%lld\n", ans);
}

int main() {
  init();
  solve();
  return 0;
}