美味佳肴题解

题意：就是N个菜品，m个菜品种类，T可以做菜的总时间。j对应菜品的编号，每个食物素材具有不新鲜度b，美味值a和做菜所需要的时间c。
食物美味值=a_i-tb_i，求T时刻，最大美味值为多少？
题解，首先我们可以举例（i<j），假设先做第i个菜在做第j个菜>先做第j个菜再做第i个菜
如图化解，
是不是我们就可以先以Ci和bj，Cj和bi来比较，从小到大排序来搞呢，然后是不是有点像01背包，只不过他的贡献是我们的a_i-tb_i，对吧，别犹豫，直接搞他啊，对了，初始化dp[0]=0,其他-INF。奥里给，造他就完了。

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
int b[maxx];
struct node
{
    int a,b,c;
    bool operator <(const node& pp){
    return c*pp.b<pp.c*b;
    }
};
ll dp[maxx];
node ans[maxx];
int main()
{
    fio;
    int n,m,t;
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++)
        cin>>b[i];
    for(int i=1;i<=m;i++)
    {
        int j;
        cin>>j>>ans[i].a>>ans[i].c;
        ans[i].b=b[j];
    }
    sort(ans+1,ans+1+m);
    mse(dp,-0x3f3f3f);
    dp[0]=0;
    for(int i=1;i<=m;i++)
        for(int j=t;j>=ans[i].c;j--)
        dp[j]=max(dp[j],dp[j-ans[i].c]+ans[i].a-j*ans[i].b);
    cout<<*max_element(dp+1,dp+1+t)<<'\n';
    return 0;
}