【每日一题】美味佳肴

戳我传送

题意：

题目描述：
小明是个大厨。他所在的餐厅每天早上都会买好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道菜肴。

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

思路：

一定的时间做一定的菜，每个菜不能分割，很容易发现是个0/1背包问题，，但是因为价值跟所完成的时间有关(即跟选取顺序有关)，所以不能按照顺序直接背包，要先排序，即做菜的顺序也很重要，虽然一定时间做了一些菜，但是做的顺序不一样答案也可能不一样。
假设i、j两道菜，应该先完成菜i:
，则有X>=Y，即 。
按照上试排序后，0/1背包即可。

0/1背包

1. ，表示时间j内做前i到菜的最大价值，也可以用滚动数组来写，就是一维 ，此时j应该反过来循环，从后往前覆盖。
2.虽然价值不会超过正的1e9，但是会比-1e9还小，所以要开ll，而且 除了 都要初始化为-1e18。
3.普通的0/1背包最后的 就是答案，但是为什么这里还要找呢，因为这题时间越多会减少价值，所以 不一定是答案。
Code：

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
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;
}
ll dp[maxn];
ll b[55],x;
struct node{
    ll a,b,c;
    bool operator<(const node&a)const{
        return b*a.c>c*a.b;
    }
}a[55];
int n,m,t;
int main() {
    read(n),read(m),read(t);
    for(int i=1;i<=n;++i) read(b[i]);
    for(int i=1;i<=m;++i) {
        read(x),read(a[i].a),read(a[i].c);
        a[i].b=b[x];
    }
    sort(a+1,a+1+m);
    fill(dp+1,dp+1+t,-0x3f3f3f3f3f3f3f3f);
    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-a[i].b*j);
    ll ans=-0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=t;++i)    ans=max(ans,dp[i]);
    printf("%lld\n",ans);
}