【题解】免费菜肴

美味菜肴

http://www.nowcoder.com/questionTerminal/312700f3777244fab148bfd95f2f5d59

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

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

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

结论是，一定存在一种最优方案 $i_1, i_2, \ldots, i_k$ ，使得对于任意 $1 \le x \lt y \le k$ ，都有 $\frac{b_{j[i_x]}}{c_{i_x}} \ge \frac{b_{j[i_y]}}{c_{i_y}}$ 。

证明如下：若不满足该条件，则必然存在一个位置 $x$ ，满足 $\frac{b_{j[i_x]}}{c_{i_x}} \lt \frac{b_{j[i_{x + 1}]}}{c_{i_{x + 1}}}$ 。

我们把 $i_x$ 和 $i_{x + 1}$ 两道菜肴拎出来，单独计算它们对答案的贡献。

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

若按照 $i_x, i_{x + 1}$ 的顺序制作菜肴，则对答案的贡献为 $a_{i_x} - (t_0 + c_{i_x}) \cdot b_{j[i_x]} + a_{i_{x + 1}} - (t_0 + c_{i_x} + c_{i_{x + 1}}) \cdot b_{j[i_{x + 1}]}$ 。

如果我们交换 $i_x$ 和 $i_{x + 1}$ 的顺序，变成按照 $i_{x + 1}, i_x$ 的顺序制作菜肴，则对答案的贡献为 $a_{i_{x + 1}} - (t_0 + c_{i_{x + 1}}) \cdot b_{j[i_{x + 1}]} + a_{i_{x}} - (t_0 + c_{i_{x + 1}} + c_{i_{x}}) \cdot b_{j[i_{x}]}$ 。

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

$\begin{aligned} & \left(a_{i_x} - (t_0 + c_{i_x}) \cdot b_{j[i_x]} + a_{i_{x + 1}} - (t_0 + c_{i_x} + c_{i_{x + 1}}) \cdot b_{j[i_{x + 1}]}\right) - \left(a_{i_{x + 1}} - (t_0 + c_{i_{x + 1}}) \cdot b_{j[i_{x + 1}]} + a_{i_{x}} - (t_0 + c_{i_{x + 1}} + c_{i_{x}}) \cdot b_{j[i_{x}]}\right) \\ = & c_{i_{x + 1}} \cdot b_{j[i_x]} - c_{i_x} \cdot b_{j[i_{x + 1}]} \end{aligned}$

由于 $\frac{b_{j[i_x]}}{c_{i_x}} \lt \frac{b_{j[i_{x + 1}]}}{c_{i_{x + 1}}}$ ，则 $c_{i_{x + 1}} \cdot b_{j[i_x]} - c_{i_x} \cdot b_{j[i_{x + 1}]} \lt 0$ 。也就是说，如果交换了 $i_x$ 和 $i_{x + 1}$ 的顺序，可以使得答案变大，故而原方案不是最优方案，证毕。

于是我们可以将所有菜肴按照 $\frac{b_{j[i]}}{c_i}$ 从大到小排序，然后再从前往后做一遍 01 背包即可。

时间复杂度 $\mathcal{O}(n + m \log m + Tm)$ 。

代码：

#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;
}