【每日一题】美味菜肴 (dp / 01背包)

Solution
题意：给出m道菜，有a,b,c属性，美味值是a-b*c,求T时间能制作出菜肴的最大价值和。

规定条件范围内的最大价值和/方案数，妥妥背包~
跟国王游戏很像，每道菜的价值跟选取的顺序有关，所以要预处理出每道菜的顺序。
考虑任意两道菜x和y的价值：

1. x煮完后再煮y :
2. y煮完后再煮x :

由于a属性与选取顺序无关，所以考虑 bc属性即可
若情况1的价值更大，移向有：
所以以此为 cmp 排序即可。
然后还要注意答案可能是负数，所以dp初始化为-1e18
设 保证答案一定是由0开始转移的，最后 ans 取 max 即可。

Code

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;

struct node{
    ll a,b,c;
}d[manx];
ll val[manx],dp[manx];

bool cmp(node x, node y){
    return x.b*y.c>y.b*x.c;
}
int main(){
    io; 
    ll n,m,t; cin>>n>>m>>t;
    for(int i=1;i<=n;i++) cin>>val[i];
    for(int i=1;i<=m;i++) cin>>d[i].b>>d[i].a>>d[i].c,d[i].b=val[d[i].b];
    for(int i=1;i<=t;i++) dp[i]=-1e18;
    sort(d+1,d+1+m,cmp);
    for(int i=1;i<=m;i++)
        for(int j=t;j>=d[i].c;j--)
            dp[j]=max(dp[j],dp[j-d[i].c]+d[i].a-d[i].b*j);
    ll ans=-1e18;
    for(int i=1;i<=t;i++) ans=max(ans,dp[i]);
    cout<<ans;
    return 0;
}