我好像忘记背包怎么写了。。写二维居然挂掉了。。改了一维才过。

题目大意：
题目解释起来比较复杂，直接贴原文链接：
https://ac.nowcoder.com/acm/problem/14704

思路：
看题目就给人浓浓的背包的感觉。
显然不可能直接背包。
我们假设最后已经得到了答案，那么我们必然会选择其中的一些菜肴，而且这些菜肴一定有固定的顺序去烹饪来使得美味值最大。
我们考虑最后答案是两种菜肴a1和a2。
最终答案有两种：ans1=a1-t1b1+a2-(t1+t2)b2 和 ans2=a2-t2b2+a1-(t1+t2)b1
要让选择顺序为a1,a2的话，我们需要令ans1>ans2
化简以后就是b1/t1 > b2/t2
那么我们只要先排序，然后问题就变成了某个菜肴选或不选的问题，就是01背包了。。

注意：
这里的一个问题是，答案可能为负数，所以我们令dp初始化为-inf，然后令dp[0]=0就可以了。
用二维数组会超内存，所以一维或者滚动数组优化一下。
代码：

#include<bits/stdc++.h>
using namespace std;
const long long inf=1e18;
int n,m,T;
long long dp[1000500];
int b1[55];
struct node{
    int x,a,c,b;
    double t;
}p[55];
bool cmp(node q,node w){
    return q.t>w.t; 
}
int main()
{
    cin>>n>>m>>T;
    for(int i=1;i<=n;i++)cin>>b1[i];
    for(int i=1;i<=m;i++){
        int j;
        cin>>j>>p[i].a>>p[i].c;
        p[i].b=b1[j];
        p[i].t=1.0*p[i].b/p[i].c;
    }
    sort(p+1,p+1+m,cmp);

        for(int j=0;j<=1000000;j++)dp[j]=-inf;

    dp[0]=0;
    for(int i=1;i<=m;i++){
        for(int j=T;j>=p[i].c;j--){
            dp[j]=max(dp[j],dp[j-p[i].c]+p[i].a-j*p[i].b);       
        }
    }
    long long ans=-inf;
    for(int i=1;i<=T;i++)ans=max(ans,dp[i]);
    cout<<ans<<endl;
    return 0;
}