【每日一题】美味菜肴

这个题目的关键是要发现他是一个贪心+dp的题目。

我们具体怎么做这道题目呢？首先我们考虑最早应该做哪些菜肴是最好的，就是要把他们全部排一个序，根据能获得的菜肴美味值。
对于编号为i和j的菜肴，他们的美味值总和在先后顺序不同的时候是这样的。
如果要i排在j前面就要使得这样的美味值大于第二种方法
具体公式是

那么我们根据他排序之后要做的就是简单的01背包了，我们考虑dp[i][j]表示前i个菜肴里面在不超过j时间内所能获得的最大美味值。
容易得到转移方程：

  dp[j]=max(dp[j],dp[j-cai[i].c]+cai[i].a-cai[i].b*j);

完整的代码如下

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,m,k,t;
int b[55];
int id[55],w[55],ti[55];
struct node{
    ll a,b,c;
}cai[55];
ll dp[1000010];
int main()
{
    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++) scanf("%d%d%d",&cai[i].b,&cai[i].a,&cai[i].c),cai[i].b=b[cai[i].b];
    auto f=[](node x,node y){
        return  x.c*y.b<y.c*x.b;
    };
    sort(cai+1,cai+1+m,f);
    memset(dp,-0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=m;i++)
        for(int j=t;j>=cai[i].c;--j)
            dp[j]=max(dp[j],dp[j-cai[i].c]+cai[i].a-cai[i].b*j);
    ll res=-9e18;
    for(int i=1;i<=t;i++) res=max(res,dp[i]);
    cout<<res;
    return 0;
}