Question

给定n个食物素材和m个食物种类，每个食物素材具有不新鲜度b，每个食物具有特定且唯一的食物素材编号为j，美味值a和做菜所需要的时间c。
食物美味值，求T时刻，最大美味值为多少？

Solution

每个食物的美味度只和他完成的时间点有关。
两个食物若默认比先做后做的区别在于:
我们对其排序，后01背包即可。
至于这里为什么是01背包而不是完全背包呢？
虽然菜还是哪道菜，他的种类没有发生变化，但是他的美味值再时刻发生变化，刚才的这道菜已经不是现在的这道菜了，他变得不那么新鲜了。

希望我能不那么菜

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 50 + 5;

struct node{
    ll a,b,t;
    bool operator < (const node& T){
        return t*T.b<T.t*b;
    }
}c[N];

int n,m,T,d[N];
ll f[maxn];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>T;
    for(int i=1;i<=n;i++) cin>>d[i];
    for(int i=1;i<=m;i++){
        ll x;cin>>x>>c[i].a>>c[i].t;
        c[i].b=d[x];
    }
    sort(c+1,c+1+m);
    memset(f,-0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=m;i++){
        for(int j=T;j>=c[i].t;j--){
            f[j]=max(f[j],f[j-c[i].t]+c[i].a-j*c[i].b);
        }
    }
    cout<<*max_element(f+1,f+1+T)<<'\n';
    return 0;
}