这题是一个 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;
}