题目

题目描述：
小明是个大厨。他所在的餐厅每天早上都会买好n件食材（每种食材的数量可以视为无限），小明从到达餐厅开始就连续工作T时间。
每道菜肴的制作需要特定的一种食材以及一段时间，但是食材一旦放久就不新鲜了，菜的美味值会降低。
第i道菜肴有三个属性ai，bi，ci，ai是该菜肴的美味值，bi是该菜肴所选食材不新鲜的速率，如果在第t时刻完成第i道菜则美味值为：ai - t * bi，完成这道菜需要ci的时间。
小明希望在这T时间内能做出菜肴使得总美味值最大，所以小明求助于你。

输入描述 ：
第1行输入三个整数n，m，T，分别代表食材种类，菜肴种类和工作时间。
第2行输入n个整数bi，代表第i个食材不新鲜的速率。
第3 - n + 2行，每行输入三个整数j，ai，ci，分别代表第i道菜肴需要的食材编号，菜肴的美味值，完成时间。
数据保证：0 < n，m ≤ 50，0 < j ≤ n，其他值均 < 1e6，美味值必须通过完整做出菜肴得到，数据保证在规定时间内至少能完整做出1道菜肴。

输出描述 ：
输出一行，一个整数，表示最大总美味值。

解析

这道题从题目可以看出这是一道01背包问题，但是和普通背包的差别就是：条件复杂了很多。
关于背包问题：
  1. 我们平常的背包问题经常会有：物品，数量（这个可能没有），权值，背包容量。
  2. 那这道题里面呢？我们知道了物品（本题的菜品），也有容量（本题的时间）。但是权值是用来衡量物品价值的，是什么呢？
  3. 是做菜耗时吗？不是！应该是每样菜对我们最终容量做出的贡献（在时间和品质上的贡献）。而要知道贡献就要用我们的数学知识了。
  4. 首先我们要知道是哪个菜的价值高，我们假设原本有 i 位置和 j 位置，假设先完成第 j 个菜的价值更大，
    则有：（左边为先做 i 再做 j，右边相反）
  5. 由此化简我们可以得到。也就是。（意思就是说：j 的价值大，这个比值就会小）
  6. 所以我们可以按照升序排列（保证价值大的在前面）。

然后又是写代码了：
  1. 按照题目要求，每个数组保存好。
  2. 按照题目要求，编辑一个cmp函数按照比值的升序排列（就会按照价值的降序排列，详情看上面的算法说明）
  3. 然后就是01背包的正常操作了。
  4. 最后选出最大的输出就好了。（有可能是负数，所以初始化都选-INF）

AC代码 

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
//代码预处理区

const int INF = 0x3f3f3f3f;
const int MAX = 50 + 7;
const int MAXT = 1e6 + 7;
int id[MAX], a[MAX], c[MAX];//菜品编号，菜品美味值，菜品完成时间
int b[MAX], food[MAX];//食材腐败速率，需要的食材编号
ll dp[MAXT];
//全局变量区

template<class T>inline void read(T& res);//整型快读函数
int cmp(int x, int y);//条件排序函数
//函数预定义区

int main() {
    int n, m, T; read(n); read(m); read(T);
    for (int i = 1; i <= n; i++) read(b[i]);
    for (int i = 1; i <= m; i++) {
        read(food[i]); read(a[i]); read(c[i]);
        id[i] = i;
    }
    //数组初始化
    sort(id + 1, id + m + 1, cmp);
    //按美味值贡献进行排序
    dp[0] = 0;
    fill(dp + 1, dp + 1 + T, -INF);
    for (int i = 1; i <= m; i++) {
        int pos = id[i];//pos为菜品编号
        for (int j = T; j >= c[pos]; j--)
            dp[j] = max(dp[j], dp[j - c[pos]] + a[pos] - j * b[food[pos]]);
    }
    //递推求解
    ll ans = -INF;
    for (int i = 1; i <= T; i++)
        ans = max(ans, dp[i]);
    printf("%lld", ans);
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
int cmp(int x, int y) {
    return c[x] * b[food[y]] < c[y] * b[food[x]];
}
//函数区