题目大意:

国家探险队长 Jack 意外弄到了一份秦始皇的藏宝图,于是,探险队一行人便踏上寻宝之旅,去寻找传说中的宝藏。

藏宝点分布在森林的各处,每个点有一个值,表示藏宝的价值。它们之间由一些小路相连,小路不会形成环,即两个藏宝点之间有且仅有一条道路。探险队从其中的一点出发,每次他们可以留一个人在此点开采

宝藏,也可以不留,然后其余的人可以分成若干队向这一点相邻的点走去。需要注意的是,如果他们把队伍分成两队或两队以上,就必须留一个人在当前点,提供联络和通讯,当然这个人也可以一边开采此地的

宝藏。并且,为了节约时间,队伍在前往开采宝藏过程中是不会走回头路的。现在你作为队长的助理,根据已有的藏宝图,请计算探险队所能开采的最大宝藏价值。

注意:在整个过程中,每个人最多只能开采一个点的宝藏。

题目分析:

和选课差不多,可以转成孩子兄弟树,也可以按照拓扑序来进行树上背包(由于一个节点有多个儿子,所以选择由儿子更新父亲)。

\(dp[i][j][0]\)表示在i节点子树中选择j个节点,i节点不选的方案,\(dp[i][j][1]\)表示i节点子树中选择j个点,i节点要选的方案.

每个节点分为两种情况:在其父节点驻守,那么背包即可,否则由儿子直接转给父亲。

code

树上背包

#include<bits/stdc++.h>
using namespace std;
const int N = 150, M = 150;
int n, m, dp[N][M][2];
int ecnt, adj[N], go[N << 1], nxt[N << 1];
int val[N], fa[N], deg[N], ans;
queue<int> que; inline void addEdge(int u, int v){
nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v;
} inline void dfs(int u, int f){
fa[u] = f;
for(int e = adj[u]; e; e = nxt[e]){
int v = go[e];
if(v == f) continue;
dfs(v, u);
deg[u]++;
}
} int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &val[i]);
for(int i = 1; i < n; i++){
int x, y; scanf("%d%d", &x, &y);
addEdge(x, y), addEdge(y, x);
}
for(int j = 1; j <= n; j++)
for(int k = 1; k <= m; k++) dp[j][k][1] = val[j];
dfs(1, 0);
while(!que.empty()) que.pop();
for(int j = 1; j <= n; j++)
if(!deg[j]) que.push(j);
while(!que.empty()){
int u = que.front(); que.pop();
int tmp[M][2];
memcpy(tmp, dp[fa[u]], sizeof tmp);
for(int j = 1; j <= m; j++){
for(int k = m - j; k >= (fa[u] ? 1 : 0); k--){ //驻守在father
dp[fa[u]][k + j][1] = max(dp[fa[u]][k + j][1], tmp[k][1] + max(dp[u][j][1], dp[u][j][0]));
}
dp[fa[u]][j][0] = max(dp[fa[u]][j][0], max(dp[u][j][1], dp[u][j][0])); //不驻守
} if(!(--deg[fa[u]]) && fa[u]) que.push(fa[u]);
}
printf("%d", max(dp[0][m][1], dp[0][m][0]));
return 0;
}

多叉树转二叉树

#include<bits/stdc++.h>
using namespace std;
const int N = 150;
int n, m;
int val[N], fa[N];
int ecnt, adj[N], nxt[N << 1], go[N << 1];
int dp[N][N][2], son[N], bro[N]; inline void addEdge(int u, int v){
nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v;
} inline void dfs(int u, int f){
fa[u] = f;
for(int e = adj[u]; e; e = nxt[e]){
int v = go[e];
if(v == f) continue;
dfs(v, u);
}
} inline int DP(int u, int k, int t){
if(!u || !k) return dp[u][k][t] = 0;
if(dp[u][k][t] != -1) return dp[u][k][t];
dp[u][k][t] = 0;
if(t == 1){ //父亲节点被选择
for(int i = 0; i <= k - 1; i++) //选择u
dp[u][k][1] = max(dp[u][k][1], DP(son[u], i, 1) + DP(bro[u], k - 1 - i, 1) + val[u]);
for(int i = 0; i <= k; i++) //不选u
dp[u][k][1] = max(dp[u][k][1], DP(son[u], i, 0) + DP(bro[u], k - i, 1));
}
else { //父亲节点未被选择 ,只能选择一边
dp[u][k][0] = max(dp[u][k][0], max(
max(DP(son[u], k - 1, 1) + val[u], DP(son[u], k, 0)),
DP(bro[u], k, 0)
));
}
return dp[u][k][t];
} int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &val[i]);
for(int i = 1; i < n; i++){
int x, y;
scanf("%d%d", &x, &y);
addEdge(x, y);
addEdge(y, x);
}
dfs(1, 0);
memset(dp, -1, sizeof dp);
for(int i = 1; i <= n; i++) bro[i] = son[fa[i]], son[fa[i]] = i;
printf("%d", max(DP(son[0], m, 1), DP(son[0], m, 0)));
}
05-11 22:11