美味菜肴 题解

一.闲谈

好吧，又是个套路题。。。

我对题面已无力吐槽。。。“第3-n+2行”明明应该是“第3-m+2行”，害我debug好久qwq

二.题解

首先，明显这是一个01背包问题（一开始看到食材无限时，以为是完全背包，结果被样例2卡了，样例出的不错。。。）

当然，我们直接打01背包是会错的，为什么？因为，我们可以获得的价值不仅与我们选了哪些菜肴有关，还和我们选这些菜肴的顺序有关

我们01背包仅仅考虑的是，按一定的顺序，选哪些菜肴能获得的最大价值，并不能处理顺序问题，怎么办呢？

考虑贪心

我们假设，我们将第i个菜肴的顺序和第j个菜肴的顺序交换后(i<j)如果，更优,就有如下式子成立:

化简下:

移项:

所以，我们按照由小到大排序后的顺序做01背包即可

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=51,M=1e6+1;
#define int long long
int a[N],b[N],c[N],d[N];
int dp[M],id[N];
inline bool kkk(int x,int y){
    return double(c[x])/b[d[x]]<double(c[y])/b[d[y]];
}
signed main(){
    int n,m,T;
    scanf("%lld%lld%lld",&n,&m,&T);
    for(int i=1;i<=n;++i){
        scanf("%lld",&b[i]);
    }
    for(int i=1;i<=m;++i){
        scanf("%lld%lld%lld",&d[i],&a[i],&c[i]);
        id[i]=i;
    }
    sort(id+1,id+m+1,kkk);
    for(int i=1;i<=m;++i){
        int v=id[i];
        for(int j=T;j>=c[v];--j){
            dp[j]=max(dp[j],dp[j-c[v]]+(a[v]-j*b[d[v]]));
        }
    }
    int ans=0;
    for(int i=0;i<=T;++i){
        ans=max(ans,dp[i]);
    }
    if(!ans){
        ans=-1e17;
        for(int i=1;i<=m;++i){
            ans=max(ans,a[i]-c[i]*b[d[i]]);
        }
    }
    printf("%lld",ans);
    return 0;
}