首页 > 编程学习 > 树上背包dp

树上背包dp

发布时间:2022/11/24 23:08:06

在这里插入图片描述
“我们终其一生不过是为了一个AC罢了”
软件安装
嗯…这个题又调了一个下午,不过俺的确对dp方程有了一些理解
这个题没啥难的,不过是这个转移方程不太好想,过于抽象了,之前一直不理解树上背包是啥,现在理解了,en…
就是说把dp[i][j]dp[i][j]dp[i][j]定义成为以iii为根节点,耗费jjj,能得到的最大价值,这没啥难的了吧?还有一个问题就是我们在对当前这个curcurcurdpdpdp的时候,一定要注意先搜一下他的子节点,这里面由于已经缩点了,并且他就是一棵树,也不用设置visvisvis数组,比较简单,也就是遍历一次就搜一次:dfs(v)dfs(v)dfs(v)
接下来我们看这个怎么用子节点来更新这个父节点
就是说这个方向一定要弄明白:
当我们用dp[k]dp[k]dp[k]更新dp[k−i]dp[k-i]dp[ki]的时候,这个更新的方向就是:
《----------向左的
啥意思,就是右方向的数更新左方向的
那么我们循环中的遍历方向就得是++++++,也就是向右走:
------------》
可能这里有点抽象,不要着急,我们来举个例子看看:
a0,a1,a2,...,ana_{0},a_{1},a_{2},...,a_{n}a0,a1,a2,...,an
当我们用ana_{n}an更新前面的数时,假设更新a2a_{2}a2,那么这个时候如果外循环是从nnn向0走的话,当走到a2a_{2}a2之后是不是要用新的a2a_{2}a2更新a2a_{2}a2左面的数?这是不对的,因为我们更新的目的是用旧状态更新新的状态,在ana_{n}an更新完a2a_{2}a2之后,a2a_{2}a2已经是新状态了,你不能再用这个新状态去更新旧状态了,相反而应该用旧的a2a_{2}a2更新,但是由于你的行进方向出错,旧的a2a_{2}a2已经被你冲掉了,你还咋更新?
然后背包问题还有一个事情,额,就是这个怎么更新的问题,注意我们这里设置的jjj是背包剩余的重量,你用子节点向父节点更新的时候,相当于往里面加物品,得用总重量把jjj减下去

for (int k= 0;k<= m - cost[cur];k++){for(int i=m-k;i<=m;i++){dp[cur][k-(m-i)] = max(dp[cur][k-(m-i)], dp[j][i] + dp[cur][k]);}}

我们里面你看那个k−(m−i)k-(m-i)k(mi)的正负号,相当于是整体在向右前进,不要写那种(k−i)(k-i)(ki)然后kkk是向右走,iii也是向右走
嗯…今天第一次用markdownmarkdownmarkdown写了一次看起来还可以的博客
具体体现在是markdownmarkdownmarkdown不是markdown
后记:若有不当欢迎指出~~
好了,贴一个ac代码:

#include<bits/stdc++.h>
using namespace std;
#define max(a,b) (a>b)?a:b
const int lengthn = 105;
const int lengthm = 505;
int weight[lengthn];
int money[lengthn];
int cost[lengthn];
int w[lengthn];
int degree[lengthn];
int dp[lengthn][lengthm];
vector<vector<int>> edge(lengthn);
vector<vector<int>> edget(lengthn);
int n, m;
int flag;
int dfn[lengthn];
int low[lengthn];
stack<int> s;
int inq[lengthn];
int color[lengthn];
int cnt = 1;
int res = 0;
void tarjan(int cur)
{dfn[cur] = cnt++;low[cur] = dfn[cur];s.push(cur);inq[cur] = 1;for (int j : edge[cur]){if (!dfn[j]){tarjan(j);low[cur] = min(low[cur], low[j]);}else if (inq[j]){low[cur] = min(low[cur], dfn[j]);}}if (low[cur] == dfn[cur]){res++;while (s.top() != cur){color[s.top()] = res;inq[s.top()] = 0;s.pop();}color[cur] = res;inq[cur] = 0;s.pop();}
}
void dfs(int cur)
{for (int j = 0; j <= m - cost[cur]; j++){dp[cur][j] = w[cur];}for (int j : edget[cur]){dfs(j);for (int k= 0;k<= m - cost[cur];k++){for(int i=m-k;i<=m;i++){dp[cur][k-(m-i)] = max(dp[cur][k-(m-i)], dp[j][i] + dp[cur][k]);}}}
}
int main(void)
{scanf_s("%d%d", &n, &m);for (int i = 1; i <= n; i++){scanf_s("%d", &weight[i]);}for (int i = 1; i <= n; i++){scanf_s("%d", &money[i]);}for (int i = 1; i <= n; i++){int a;scanf_s("%d", &a);if (i != a && a != 0){edge[a].push_back(i);//加一个超级源点就可以了,这个题的超级源点正好是那个}}for (int i = 1; i <= n; i++){if (!dfn[i])tarjan(i);}for (int i = 1; i <= n; i++){for (int j : edge[i]){if (color[j] != color[i]){edget[color[i]].push_back(color[j]);degree[color[j]]++;}}}for (int i = 1; i <= n; i++){cost[color[i]] += weight[i];w[color[i]] += money[i];}for (int i = 1; i <=res; i++){if(!degree[i])edget[0].push_back(i);}//tarjan缩点dfs(0);int ans = *max_element(dp[0], dp[0] + m + 1);printf("%d", ans);
}

本文链接:https://www.ngui.cc/article/show-701433.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000