每日一题6.16(树上背包+状态机dp)

495684945

力扣3562   力扣的题解质量还是太高了，有大佬灵茶山艾府(0x3f)写题解
https://leetcode.cn/problems/max ... counts/description/

Fengyj

[C++] 纯文本查看 复制代码

class Solution {
public:
    int maxProfit(int n, vector<int>& present, vector<int>& future, vector<vector<int>>& hierarchy, int budget) {
        vector<vector<int>>adj(n);
        for(auto &e:hierarchy){
            adj[e[0]-1].push_back(e[1]-1);
        }

        auto dfs=[&](this auto dfs,int u)->vector<array<int,2>>{
            vector<array<int,2>>g(budget+1);

            for(auto v:adj[u]){
                auto ff = dfs(v);

                for(int j=budget;j>=0;j--){
                    for(int jj=0;jj<=j;jj++){
                        for(int k=0;k<=1;k++){
                            g[j][k]=max(g[j][k],g[j-jj][k]+ff[jj][k]);
                        }
                    }
                }
            }

            vector<array<int,2>>f(budget+1);

            for(int j=0;j<=budget;j++){
                for(int k=0;k<2;k++){
                    int cost=present[u]/(k+1);
                    if(j>=cost){
                        f[j][k]=max(g[j][0],g[j-cost][1]-cost+future[u]);
                    }
                    else{
                        f[j][k]=g[j][0];
                    }
                }
            }
            return f;
        };

        return dfs(0)[budget][0];
    }
};