题目描述

小明是个大厨，早上起来他开始一天的工作。他所在的餐厅每天早上都会买好n件食材（每种食材的数量可以视为无限），小明从到达餐厅开始就连续工作T时间。每道菜肴的制作需要特定的一种食材以及一段时间，但是食材一旦放久就不新鲜了，菜的美味值会降低。第i道菜肴有三个属性ai，bi，ci，ai是该菜肴的美味值，bi是该菜肴所选食材不新鲜的速率，如果在第t时刻完成第i道菜则美味值为：ai-t*bi，完成这道菜需要ci的时间。小明希望在这T时间内能做出菜肴使得总美味值最大，所以小明求助于你。

输入描述:

第1行输入三个整数n，m，T，分别代表食材种类，菜肴种类和工作时间。
第2行输入n个整数bi，代表第i个食材不新鲜的速率。
第3-n+2行，每行输入三个整数j，ai，ci，分别代表第i道菜肴需要的食材编号，菜肴的美味值，完成时间。
数据保证：0<n,m≤50，0<j≤n，其他值均<106，美味值必须通过完整做出菜肴得到，数据保证在规定时间内至少能完整做出1道菜肴。

输出描述:

输出一行，一个整数，表示最大总美味值。

题解

背包+贪心
上来就背包肯定是错的, 因为这里多了一个时间的限制, 价值随着时间而变化。因此需要考虑贪心策略下背包。对于物品进入放入背包的时间顺序，必然是用时越短的物品越先放进去的策略最优。所以我们排个序之后再去跑背包就行了QAQ

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node{
    int a,b,c;
    bool operator < (const node &rhs)const{
        return rhs.c*b>rhs.b*c;
    }
}s[55];
long long dp[N];
int b[55];
int main(){
    int n,m,T;
    scanf("%d%d%d",&n,&m,&T);
    for(int i=1;i<=n;++i){
        scanf("%d",&b[i]);
    }
    for(int i=1;i<=m;++i){
        int id;
        scanf("%d%d%d",&id,&s[i].a,&s[i].c);
        s[i].b=b[id];
    }
    sort(s+1,s+1+m);
    memset(dp,-0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=m;++i){
        for(int j=T;j>=s[i].c;--j){
            dp[j]=max(dp[j],dp[j-s[i].c]+s[i].a-j*s[i].b);
        }
    }
    sort(dp+1,dp+T+1);
    cout<<dp[T]<<endl;
}