美味菜肴

题意：有n种食材，m种菜肴，每种菜肴给出所需食材和美味值和制作时间，因为每种食材以a[i]的速率变得不新鲜，求在t秒总美味值最大为多少？

注意：最大总美味值可能为负。

思路：贪心+01背包
贪心：
设二种相邻菜肴，第一种所需食材变的不新鲜的速率为w[i].a,美味值为w[i].b，制作时间为w[i].c,第二种所需食材变的不新鲜的速率为w[i+1].a,美味值为w[i+1].b，制作时间为w[i+1].c;
如果顺序正确则需满足:
w[i].b-w[i].aw[i].c+w[i+1].b-(w[i].c+w[i+1].c)w[i+1].a
<w[i+1].b-w[i+1].aw[i+1].c+w[i].b-(w[i].c+w[i+1].c)w[i].a
化简为：w[i+1].cw[i].a>w[i].cw[i+1].a

01dp:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i].c]+w[i].b-w[i].a*j);

代码：

#include<bits/stdc++.h>
#define inf 1000000007

using namespace std;

typedef long long ll;

struct w
{
    ll a, b, c;
}w[105];

int a[105];
ll dp[1000005];

bool cmp(struct w a,struct w b)
{
    return a.a*b.c>b.a*a.c;
}

int main()
{
    int n, m, t;
    scanf("%d %d %d",&n,&m,&t);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld %lld %lld",&w[i].a,&w[i].b,&w[i].c);
        w[i].a=a[w[i].a];
    }
    sort(w+1,w+m+1,cmp);
    fill(dp,dp+1000005,-100000007);
    dp[0]=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=t;j>=0;j--)
        {
            if(j>=w[i].c)
            dp[j]=max(dp[j],dp[j-w[i].c]+w[i].b-w[i].a*j);
        }
    }
    ll ma=-10000000007;
    for(int i=1;i<=t;i++)
    {
        ma=max(ma,dp[i]);
    }
    printf("%lld\n",ma);
    return 0;
}