题解 | 奶油蛋糕的进阶配方

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

struct Cake{
    int door,sweet,energy;
};

int main(){
    int n,sweet0,energy0,num;  //蛋糕的种类数、初始甜度等级、初始体力值、最大制作数量
    cin>>n>>sweet0>>energy0>>num;

    vector<Cake> cakes(n);
    vector<int> door(n),sweet(n),energy(n);

    for(int i=0;i<n;i++) cin>>door[i];
    for(int i=0;i<n;i++) cin>>sweet[i];
    for(int i=0;i<n;i++) cin>>energy[i];
    for(int i=0;i<n;i++) cakes[i]={door[i],sweet[i],energy[i]};

    sort(cakes.begin(),cakes.end(), [](const Cake& a,const Cake& b){
         return a.door<b.door;
    });

    vector<vector<long long>> dp(num+1, vector<long long>(energy0+1,-1));
    /*
       0  1  2        energy0
    0  -1 -1 -1  ...   -1
    1  -1
    2  -1
        .
        .
        .
   num -1       ...    -1
                           */
    dp[0][0]=(long long)sweet0;
    /*
       0       1  2        energy0
    0  sweet0 -1 -1  ...   -1
    1  -1
    2  -1
        .
        .
        .
   num -1       ...        -1
                           */
    //每块蛋糕
    for(int i=0;i<n;i++){
        //行，逆序遍历
        for(int j = num ; j>=1 ; j--){
            //01背包以energy为V
            for(int energy_now = energy0 ; energy_now >= cakes[i].energy ; energy_now--){                
                /*
                    j-1  做这个蛋糕之前做的蛋糕数量
                    energy_now - cakes[i].energy  做这个蛋糕之前消耗的体力
                    dp[j-1][energy_now - cakes[i].energy]	做这个蛋糕之前的甜度
                */
                if(dp[j-1][energy_now - cakes[i].energy] >= cakes[i].door){  //做蛋糕之前的甜度，够不够门槛？
                /*
                    dp[j][energy_now]  
                    当前记录的（做j个蛋糕、消耗energy_now体力）的最大甜度
                    dp[j-1][energy_now - cakes[i].energy] + cakes[i].sweet
                    如果做了这个蛋糕，新甜度 = 之前甜度 + 这个蛋糕的提升
                */
                    dp[j][energy_now] = max(dp[j][energy_now] , dp[j-1][energy_now-cakes[i].energy]+ cakes[i].sweet);
                }
            }
        }
    }
    
    long long max_sweet = sweet0;
    int count = 0;

    for(int j=0;j<=num;j++){
        for(int energy_now=0;energy_now<=energy0;energy_now++){
            if(dp[j][energy_now] > max_sweet){
                max_sweet = dp[j][energy_now];
                count = j;
            }else if(dp[j][energy_now] == max_sweet){
                if(count > j) count = j;
            }
        }
    }
    
    cout <<max_sweet<<" "<<count<<endl;
    return 0;
}