【dp套dp+进阶限制背包】题解：bag_树形依赖背包_动态规划dp_算法竞赛_C++

文章目录题目描述题解Code题目描述有一个背包和n nn个物品要把某些物品彼此压着放在背包里。背包最大承重为S SS。已知第i ii个物品放上去的时间i n i in_iini​拿走的时间o u t i out_iouti​重量w i w_iwi​承重s i s_isi​价值v i v_ivi​i n i o u t i in_i out_iini​outi​。对于同一时刻有多个物品进出的话顺序任意。如果将一个物品放入背包必须满足以下要求在i n inin时间进放在最上面。o u t outout时间出出的时候他在最上面并且得到价值v vv。当他在背包内时他上方的物品的重量必须时刻小于等于s i s_isi​。它也可以不放入背包则得不到价值。问你可以得到的最大价值。n ≤ 500 n \le 500n≤500S ≤ 1000 S \le 1000S≤1000题解发现这道题困难的地方在于处理许多限制放入和取出的时间限制、同一时刻容量限制、总容量限制等……而且因为满足的是一个类似栈的关系顺序取出时必须在堆顶的限制 和 其上面的总容量不超过s i s_isi​的限制 要看的方向还是相反的所以题解里有很重要的一步先把所有物品按照拿走的时间从小到大排序拿走的时间相同就按照放上去的时间从大到小。那么一件物品上方的物品就一定会在它的前面。注意到选出的物品在时间轴上[ i n , o u t ] [in,out][in,out]的区间关系只能是包含或不交即选择的物品线段于时间轴上构成一个树形结构。发现很好的性质是树上的层级关系也正好对应了栈内的上下关系然后因为数据范围也不大考虑背包 dp设f [ i ] [ j ] f[i][j]f[i][j]表示i ii及其上面物品在所有时刻最大重量为j jj时的最大收益转移考虑枚举i ii上面的物品k kk尝试能不能把k kk放到i ii上面注意k kk上方也可以放物品i , k i,ki,k层间不能有其它的物品除去i ii选择的物品k kk及其上面物品的重量范围应该≤ min ⁡ ( s i , j − w i ) \le \min(s_i, j-w_i)≤min(si​,j−wi​)则问题转化为在上面即下标k i kiki找最大收益之和由于[ i n i , o u t i ] [in_i,out_i][ini​,outi​]中间可能有多个不交的合法的线段k kk为了完全统计考虑再在时间轴上做一次 dp设g [ t ] g[t]g[t]表示时间t tt之前已经结束的所有“上方物品组合”能提供的最大收益。这些物品组合在时间上互不重叠并且总重量满足某个限制。那么考虑按照时间顺序从前往后枚举上层的k kk转移除了f [ k ] [ min ⁡ ( s i , j − w i ) ] f[k][\min(s_i,j-w_i)]f[k][min(si​,j−wi​)]外还要加上k kk之前结束的物品g [ i n k ] g[in_k]g[ink​]注意因为区间不交所以应满足i n i ≤ i n k in_i \le in_kini​≤ink​更新时把g [ i n k ∼ o u t k − 1 ] g[in_k \sim out_k-1]g[ink​∼outk​−1]直接向前继承为相等的值在g [ o u t k ] g[out_k]g[outk​]处记录k kk的贡献这样可以满足取出时的限制。注意因为g gg数组仅辅助当前( i , j ) (i,j)(i,j)的转移所以要及时清空时间复杂度为O ( n 2 ⋅ S ) O(n^2 \cdot S)O(n2⋅S)实现时有一个很巧妙的操作设置一个“哨兵结点”n 1 n1n1[ 0 , o u t n 1 ] [0,out_n1][0,outn​1]容量限制为S SS这样直接输出f [ n 1 ] f[n1]f[n1]就是答案其实本题本质上可以转化为树形依赖背包或时间轴上的区间 DP。问题转化嵌套区间形成树由于物品放入时放在最上面拿出时也必须在最上面所以物品的进出时间形成了一个合法的栈式结构任意两个物品的生存区间[ i n i , o u t i ] [in_i, out_i][ini​,outi​]和[ i n j , o u t j ] [in_j, out_j][inj​,outj​]要么完全不相交要么一个完全包含另一个即嵌套。这恰好构成一片森林每个物品可以看作一个节点它的直接子节点是那些直接嵌套在它里面、且不被其他物品包含的物品。再添加一个虚拟根节点区间覆盖所有承重为背包总承重S SS重量0 00价值0 00森林就变成了一棵树。约束如果选择了某个物品i ii那么它的所有祖先都必须被选择因为要放入i ii必须先放入包含它的物品。对于物品i ii它内部嵌套的所有物品即它的后代的总重量不能超过它的承重s i s_isi​因为这些物品在它上方。虚拟根节点的容量是S SS即所有最外层物品虚拟根的直接子节点的总重量不能超过S SS。于是问题变为在一棵树上选择一些节点选了子节点必须选父节点每个节点i ii有一个重量w i w_iwi​价值v i v_ivi​并且它的所有子节点直接子节点组成的子树的总重量不能超过s i s_isi​求最大总价值。Code#includebits/stdc.husingnamespacestd;typedeflonglongll;intf[505][1005],g[1005];structNode{intin,out,w,v,s;booloperator(Node p1)const{if(outp1.out)returninp1.in;returnoutp1.out;}}a[505];voidsolve(){intn,S;cinnS;for(inti1;in;i){cina[i].ina[i].outa[i].wa[i].sa[i].v;}sort(a1,an1);a[n1]{0,a[n].out1,0,0,S};//n1用于统计答案for(inti1;in1;i){for(intja[i].w;jS;j){for(intu0;ua[n].out1;u)g[u]0;//清空intptra[i].in;for(intk1;ki-1;k){if(a[i].ina[k].in){while(ptra[k].out){ptr;g[ptr]g[ptr-1];//同一线段内直接继承}g[ptr]max(g[ptr],g[a[k].in]f[k][min(a[i].s,j-a[i].w)]);}}f[i][j]g[ptr]a[i].v;//最后实现转移此时的ptr一定范围最大包含所有最优结果}}coutf[n1][S]\n;}signedmain(){freopen(bag.in,r,stdin);freopen(bag.out,w,stdout);ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);solve();return0;}