背包(一般是(01)背包吧)与树形(DP)的结合,第一维通常是节点编号,第二维通常是背包体积.由子节点向父节点转移的时候,就是一个普通的背包问题.
(T1):选课/(The) (more), (The) (Better)
题意:给定一个(n)个节点的森林,带点权,选(m)个点的最大点权和,要求选子节点必须先选父节点.
分析:新建一个虚根,森林变成树.套路地,设(f[i][j])表示以(i)点为根的子树内选择(j)个点的最大点权和.先不考虑父节点必须选的话,(f[u][j]=max(f[u][j],f[u][j-k]+f[v][k])),最后再考虑要先选父节点,(f[u][j]=f[u][j-1]+a[u]).
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=305;
int n,m,a[N],f[N][N];
int tot,head[N],nxt[N],to[N];
inline void add(int a,int b){
nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void dfs(int u,int fa){
for(int i=head[u];i;i=nxt[i]){
int v=to[i];dfs(v,u);
for(int j=m;j>=0;--j)
for(int k=j;k>=0;--k)
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
}
if(u!=1){//如果不是虚根,则选子节点时必须要选这个根节点
for(int j=m;j>=1;--j)f[u][j]=f[u][j-1]+a[u];
}
}
int main(){
while(1){
n=read();m=read();if(!n&!m)break;
tot=0;memset(head,0,sizeof(head));
memset(f,0,sizeof(f));
for(int i=2;i<=n+1;++i){//把1号节点当做虚根,其他节点2~n+1
int x=read()+1;a[i]=read();
add(x,i);
}
dfs(1,0);
printf("%d
",f[1][m]);
}
return 0;
}
(T2):有线电视网
题意:给定一棵带边权,叶子结点带点权的有根树.问从根结点出发使得权值和不为负最多能到达的叶子结点个数.
分析:套路地,设(f[i][j])表示以(i)为根的子树内选出(j)个叶子节点的最大权值和.则(f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-w[i])).
可以先预处理出每个节点的子树内有多少个叶子节点,那么对于叶子节点初始化(f[i][1]=a[i].),答案就是最大的(j)满足(f[1][j]>=0).
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=3005;
int n,m,a[N],size[N],f[N][N],yz[N];
int tot,head[N],nxt[N],to[N],w[N];
inline void add(int a,int b,int c){nxt[++tot]=head[a];head[a]=tot;to[tot]=b;w[tot]=c;}
inline void dfs(int u,int fa){
size[u]=1;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];dfs(v,u);
size[u]+=size[v];yz[u]+=yz[v];
}
if(size[u]==1){
yz[u]=1;
f[u][1]=a[u];
}
}
inline void dp(int u,int fa){
for(int i=head[u];i;i=nxt[i]){
int v=to[i];dp(v,u);
for(int j=yz[u];j>=1;--j){
for(int k=1;k<=min(j,yz[v]);++k){
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-w[i]);
}
}
}
}
int main(){
n=read();m=read();
for(int i=1;i<=n-m;++i){
int sum=read();
for(int j=1;j<=sum;++j){
int x=read(),y=read();
add(i,x,y);
}
}
for(int i=n-m+1;i<=n;++i)a[i]=read();
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)f[i][j]=-1e9;
dfs(1,0);dp(1,0);
for(int j=m;j>=0;--j)if(f[1][j]>=0){printf("%d
",j);break;}
return 0;
}
(T3):重建道路
题意:给定一棵(n)个节点的树,求留下一棵(m)个结点的子树，最少需要切断几条边?
分析:套路地,设(f[i][j])表示以(i)为根的子树内留下(j)个节点最少需要切断的边数.则(f[u][j]=min(f[u][j],f[v][k]+f[u][j-k])),发现因为要考虑(u->v)这条边留不留的各种情况,然后就写挂了.
正难则反,设(f[i][j])表示以(i)为根的子树内丢弃(j)个节点最少需要切断的边数.这个就可以(f[u][j]=min(f[u][j],f[v][k]+f[u][j-k]))这样转移了.初始化(f[u][size[u]]=1)(即相当于整颗子树都不要,直接切掉最上面那一条边即可).
然后还是设(g[i][j])表示以(i)为根的子树内留下(j)个节点最少需要切断的边数.那么(g[i][j]=f[i][size[i]-j]+(fa==root?0:1)),即留下(j)个节点相当于丢掉(size[i]-j)个节点,然后如果(i)的父节点不是(虚)根节点((0))的话,即这条边是存在的,需要切断.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=200;
int n,m,ans,size[N],f[N][N],g[N][N];
int tot,head[N],nxt[N],to[N];
inline void add(int a,int b){
nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void dfs1(int u,int fa){
size[u]=1;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];dfs1(v,u);
size[u]+=size[v];
}
f[u][size[u]]=1;
}
inline void dfs2(int u,int fa){
for(int i=head[u];i;i=nxt[i]){
int v=to[i];dfs2(v,u);
for(int j=size[u];j>=1;--j)
for(int k=1;k<=min(size[v],j);++k)
f[u][j]=min(f[u][j],f[u][j-k]+f[v][k]);
}
}
inline void dfs3(int u,int fa){
g[u][size[u]]=(fa^0?1:0);
for(int i=1;i<size[u];++i)
g[u][i]=f[u][size[u]-i]+(fa^0?1:0);
for(int i=head[u];i;i=nxt[i])dfs3(to[i],u);
}
int main(){
n=read();m=read();
for(int i=1;i<n;++i){
int a=read(),b=read();
add(a,b);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)f[i][j]=g[i][j]=1<<30;
dfs1(1,0);dfs2(1,0);dfs3(1,0);ans=1<<30;
for(int i=1;i<=n;++i)ans=min(ans,g[i][m]);
printf("%d
",ans);
return 0;
}
发现树上背包问题有个通用套路,状态一般都是(f[i][j])表示以(i)为根的子树内.....(j)个节点的......,然后一般先要(dfs)预处理出一些东西,然后对叶子节点初始化,最后再(dfs)一次从下往上状态转移即可.