树形dp+树形依赖背包

57 阅读 0 评论 38 点赞

我是靠谱客的博主凶狠芝麻，最近开发中收集的这篇文章主要介绍树形dp+树形依赖背包，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

最近集训队大佬开了树形依赖背包的讲座,感觉还是学到了东西,就是对树形dp的理解方式更多了一种

首先接触到了两种树形dp的写法:第一种是直接在树上进行dp,另一种是在dfs序上进行dp,我较偏于后者,后者想法可以很清晰,

当然大佬们请自动略过

1.hdu1561(树形依赖背包裸题)

解法1:dp[i][j]代表选取范围为 dfs序大于等于i的所有点所能得到的最大值(这个定义..非常不准确,正着来的话..我还没想清楚细节)

能转移到dp[i][j]的点只有两种情况,运用01背包的思想,选择这个点,或者不选择这个点,

即dp[i][j]=max(dp[i+1][j-w[x]]+v[x],dp[i+size[x]][j]);

#include<bits/stdc++.h>
using namespace std;
const int N=300;
vector<int>g[N];
int now,pos[N],r[N],size[N];
void dfs(int u){
pos[++now]=u;size[u]=1;
for(auto v:g[u]) dfs(v),size[u]+=size[v];
r[u]=now;
}
int dp[N][N],v[N];
int main(){
int n,m,a,b;
while(~scanf("%d%d",&n,&m)){
if(n==0&&m==0) break;now=0;
for(int i=1;i<=n+1;i++) for(int j=1;j<=n+1;j++) dp[i][j]=0;
for(int i=0;i<=n;i++) g[i].clear();
for(int i=1;i<=n;i++){
scanf("%d%d",&a,&v[i]);
g[a].push_back(i);
}
dfs(0);m++;
for(int i=n+1;i;i--){
int x=pos[i];
for(int j=1;j<=m;j++)
dp[i][j]=max(dp[i+1][j-1]+v[x],dp[i+size[x]][j]);
}
printf("%dn",dp[1][m]);
}
return 0;
}

View Code

解法2:运用树形dp独特的优化,枚举有效的元素

dp[i][j]代表在以i为根的子树中选择j个元素所能容纳的最大值

#include<bits/stdc++.h>
using namespace std;
const int N=300;
vector<int>g[N];
int now,pos[N],l[N],siz[N];
int dp[N][N],v[N],n,m,a;
void dfs(int u){
siz[u]=1;dp[u][1]=v[u];
for(auto v:g[u]){
dfs(v);
for(int i=siz[u];i>=1;i--)
for(int j=0;j<=siz[v]&&i+j<=m;j++){
dp[u][i+j]=max(dp[u][i+j],dp[u][i]+dp[v][j]);
}
siz[u]+=siz[v];
}
//枚举有效的元素 
}
int main(){
while(~scanf("%d%d",&n,&m)){
if(n==0&&m==0) break;now=0;
memset(dp,0,sizeof(dp));
memset(siz,0,sizeof(siz));
for(int i=0;i<=n;i++) g[i].clear();
for(int i=1;i<=n;i++){
scanf("%d%d",&a,&v[i]);
g[a].push_back(i);
}
m++;dfs(0);
printf("%dn",dp[0][m]);
}
return 0;
}

View Code

解法3:讲解的全局动归和正着来的dfs序.......觉得他们给的代码是错的,反正我当模板代进去,样例都过不了....

2.codeforces 815C

解法:运用树形dp的独特优化,达到n^2的复杂度,想一下这些串的链接方式,在考虑儿子和父亲合并的时候,可能

1.父亲不用券,儿子也不用券,

2.父亲用券,儿子不用券

3.父亲用,儿子也用,

只有这三种情况

所以用二维的枚举有效元素,即可解决,注意遍历的顺序

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e3+10;
vector<int>g[N];int n,b,x,now;
int c[N],d[N],pos[N],siz[N];
int dp1[N][N],dp2[N][N];
//dp1用券,dp2不用券 
void dfs(int u){
dp2[u][0]=0;siz[u]=1;
dp1[u][1]=c[u]-d[u];dp2[u][1]=c[u];
for(int z=0;z<g[u].size();z++){
int v=g[u][z];dfs(v);
for(int i=siz[u];i>=0;i--)
for(int j=0;j<=siz[v];j++){
dp1[u][i+j]=min({dp1[u][i+j],dp1[u][i]+dp1[v][j],dp1[u][i]+dp2[v][j]});
dp2[u][i+j]=min(dp2[u][i+j],dp2[u][i]+dp2[v][j]);
}
siz[u]+=siz[v];
}
}
int main(){
memset(dp1,0x3f,sizeof(dp1));
memset(dp2,0x3f,sizeof(dp2));
scanf("%d%d",&n,&b);scanf("%d%d",&c[1],&d[1]);
for(int i=2;i<=n;i++){
scanf("%d%d%d",&c[i],&d[i],&x);
g[x].push_back(i);
}
dfs(1);
for(int i=n;i>=1;i--){
if(dp1[1][i]<=b||dp2[1][i]<=b) {
printf("%dn",i);return 0;
}
}
printf("0n");
return 0;
}

View Code

3.（NAIPC2018）I - Red Black Tree

题意:一棵树,n个点,m个红点,问选择k个点的子集数(且保证子集里的元素不互为祖先)

解法:

　　(1)树形dp

　　运用枚举子树的有效元素,f[i][j]代表以i为根的子树中选取j个红点的方案数,考虑该点取还是不取即可解决

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=2e5+10;
vector<int>g[N];int clr[N];
int dp[N][1100],siz[N],n,m,x,h[N];
void dfs(int u){
siz[u]=clr[u];dp[u][0]=1;
for(auto v:g[u]){
dfs(v);
for(int i=0;i<=siz[u]+siz[v];i++) h[i]=0;
for(int i=0;i<=siz[u]&&i<=m;i++)
for(int j=0;j<=siz[v]&&i+j<=m;j++){
h[i+j]=(1ll*dp[u][i]*dp[v][j]+h[i+j])%mod;
}
for(int i=0;i<=siz[u]+siz[v];i++) dp[u][i]=h[i];
siz[u]+=siz[v];
}
dp[u][clr[u]]++;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=2;i<=n;i++){
scanf("%d",&x);
g[x].push_back(i);
}
for(int i=1;i<=m;i++) scanf("%d",&x),clr[x]=1;
dfs(1);
for(int i=0;i<=m;i++) printf("%dn",dp[1][i]);
return 0;
}