【每日一题】美味佳肴

01背包、排序
很容易看出来这是一个01背包，但是因为价值跟所完成的时间有关(即跟选取顺序有关)，所以不能按照顺序直接背包，要先排序。
考虑第i个和第j个两个菜，假设先完成第i个菜的价值更大，则有

化简后得到
按照上式排序后，01背包即可。
注意答案可能为负，dp数组除dp[0]外应赋为无穷小

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[1<<20];
ll b[1<<20];
struct node{
    ll b,a,c;
}a[1<<20];
int main(){
    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++) cin>>a[i].b>>a[i].a>>a[i].c,a[i].b=b[a[i].b];
    sort(a+1,a+1+m,[](node x,node y){
        return x.b*y.c>x.c*y.b;
    });
    for(int i=1;i<=T;i++) dp[i]=-1e18;
    for(int i=1;i<=m;i++){

        for(int l=T;l>=a[i].c;l--){
            dp[l]=max(dp[l],dp[l-a[i].c]+a[i].a-l*a[i].b);
        }
    }
    ll ans=-1e18;
    for(int i=1;i<=T;i++) ans=max(ans,dp[i]);
    cout<<ans<<endl;

    return 0;
}