Solution

题面把意思说的比较清楚，其实可以比较明显的知道，这是一个从n件物品选一些出来，需要收益最大。挺明显的01背包，但是直接按照01背包来做确实错误的。想想为什么？没错，背包问题，是动态规划的过程，动态规划需要满足两个性质，最优子结构和无后效性。显然这个题目直接做不满足无后效性，改变做菜顺序，带来的收益明显不同，那我们就要想想办法去让这个收益最大化，才能保证无论如何更换顺序，保证当前求解的动态规划都是利润最大的。
那么显然，我们选定2个菜品去做它。假设为A，B，那么向A后B得到的利润就是
那么与之对应向B后A利润为 可以对比两个式子很明显发现，前面加法都是一样的，带来的差异只有后面乘积部分，那么我们需要让最终利润最大，那么就是后面减掉的越小越先做。那么对与这道菜，如果你选择要做，顺序就已经固定了，解决了做菜顺序，第二步就是去求解最大利润，通过 表示在前i道菜用了j分钟的最大收益，因为题面数据规模问题，必须使用滚动数组或者直接压掉第一维，这个与01背包压缩内存类似。

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 55;
const int M = 1e6 + 7;
ll tmp[N];
struct Node {
    ll a, b, c;
    bool operator < (Node a) { //运算符重载
        return c * a.b < a.c* b;
    }
}a[N];
ll dp[M];

int main() {
    int n = read(), m = read(), t = read();
    for (int i = 1; i <= n; ++i)    tmp[i] = read();
    for (int i = 1; i <= m; ++i) {
        a[i].b = tmp[read()];
        a[i].a = read();
        a[i].c = read();
    }
    sort(a + 1, a + 1 + m);
    memset(dp, -0x3f, sizeof(dp)); //初始化负无穷大
    dp[0] = 0;

    // 01背包
    for (int i = 1; i <= m; ++i)
        for (int j = t; j >= a[i].c; --j)
            dp[j] = max(dp[j], dp[j - a[i].c] + a[i].a - j * a[i].b);
    ll ans = -1e16;
    for (int i = 1; i <= t; ++i)
        ans = max(ans, dp[i]);
    printf("%lld\n", ans);
    return 0;
}