3562. 折扣价交易股票的最大利润
题目链接：3562. 折扣价交易股票的最大利润
代码如下：
//参考链接：https://leetcode.cn/problems/maximum-profit-from-trading-stocks-with-discounts/solutions/3685504/shu-shang-bei-bao-zhuang-tai-ji-dppython-2q7bclassSolution{public:intmaxProfit(intn,vector<int>&present,vector<int>&future,vector<vector<int>>&hierarchy,intbudget){vector<vector<int>>g(n);for(auto&e:hierarchy){g[e[0]-1].push_back(e[1]-1);}autodfs=[&](auto&&dfs,intx)->array<vector<int>,2>{//计算从x的所有儿子子树y中，能得到的最大利润之和vector<int>sub_f[2]{vector<int>(budget+1,INT_MIN/2),vector<int>(budget+1,INT_MIN/2)};sub_f[0][0]=sub_f[1][0]=0;for(inty:g[x]){autofy=dfs(dfs,y);for(intk=0;k<2;k++){vector<int>nf(budget+1,INT_MIN/2);nf[0]=0;for(intjy=0;jy<=budget;jy++){intres_y=fy[k][jy];if(res_y<0){//物品价值为负数，一定不选continue;}for(intj=jy;j<=budget;j++){nf[j]=max(nf[j],sub_f[k][j-jy]+res_y);}}sub_f[k]=move(nf);}}array<vector<int>,2>f;for(intk=0;k<2;k++){//不买x，转移来源为sub_f[0],因为对于子树来说，父节点一定不买f[k]=sub_f[0];intcost=present[x]/(k+1);//买x，转移来源为sub_f[1]，因为对于子树来说，父节点一定买for(intj=cost;j<=budget;j++){f[k][j]=max(f[k][j],sub_f[1][j-cost]+future[x]-cost);}}returnf;};returnranges::max(dfs(dfs,0)[0]);}};
