例1：没有上司的舞会https://www.luogu.com.cn/problem/P1352
明显的树形结构
三种状态
1、上司去，而剩下的这个上司的职员就不会去。
2、不去，而那个职员去
3、上司不去，而那个职员也不去。
核心代码（f[v][0/1]是已经迭代出来的了）
f[u][0]+=maxx(f[v][1],f[v][0]); f[u][1]+=f[v][0];
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; #define N 6005 int f[N][2],st,w[N]; int n,m; int maxx(int x,int y){ return x>y?x:y; } vector<int>g[N]; bool vis[N]; void dfs(int u,int fa){ f[u][0]=0;f[u][1]=w[u]; int siz=g[u].size(); for(int i=0;i<siz;i++){ int v=g[u][i]; if(v==fa)continue; dfs(v,u); f[u][0]+=maxx(f[v][1],f[v][0]); f[u][1]+=f[v][0]; } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1,u,v;i<=n;i++){ scanf("%d%d",&u,&v); if(u==0)continue; vis[u]=1; g[v].push_back(u); } for(int i=1;i<=n;i++){ if(!vis[i]){ st=i;dfs(st,0);break; } } printf("%d ",maxx(f[st][0],f[st][1])); return 0; }
类似于有依赖的背包
设f(i)(j)表示在以 i 为根的子树中，选择 j 个点并且一定选择 i 的最大价值。
这里以0节点为开始的根
把选课前需要学的课与其连边（若没有要学的和0连边）
很明显，f(i)(1)就是其自己学分
然后转移类似01背包（倒序）
for(int j=m+1;j>=1;j--) for(int k=0;k<j;k++) f[x][j]=maxx(f[x][j],f[y][k]+f[x][j-k]);
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define N 1005 using namespace std; int n,m,f[N][N]; vector<int>g[N]; int maxx(int x,int y){ return x>y?x:y; } void dfs(int x){ int siz=g[x].size(); for(int i=0;i<siz;i++){ int y=g[x][i];dfs(y); for(int j=m+1;j>=1;j--) for(int k=0;k<j;k++) f[x][j]=maxx(f[x][j],f[y][k]+f[x][j-k]); } } int main(){ scanf("%d%d",&n,&m) ; for(int i=1,x;i<=n;i++){ scanf("%d",&x); scanf("%d",&f[i][1]); g[x].push_back(i); } dfs(0); printf("%d ",f[0][m+1]); return 0; }
一棵二叉树，边上有苹果，给定需要保留的边数量，求出最多能留住多少苹果。
维护子树大小siz[ ]
为什么是f[u][i-j-1]而不是f[u][i-j]
为前文提到了，保留一条边必须保留从根节点到这条边路径上的所有边，那么如果你想从u的子节点v的子树上留边的话，也要留下u,v之间的连边
那么取值范围k为什么要小于等于i-1而不是i呢？
同上，因为要保留u,v连边
对了，别忘了i,j要倒序枚举因为这是01背包
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<utility> using namespace std; #define N 105 inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } int f[N][N],siz[N]; int n,m; vector< pair<int,int> >g[N]; void dfs(int x,int fa){ for(int i=0;i<g[x].size();i++){ int y=g[x][i].first; if(y==fa)continue; dfs(y,x); siz[x]+=siz[y]+1; for(int j=min(siz[x],m);j>0;j--) for(int k=min(j-1,siz[y]);k>=0;k--) f[x][j]=max(f[x][j],f[x][j-k-1]+f[y][k]+g[x][i].second); } } int main(){ n=read();m=read(); for(int i=1,x,y,z;i<n;i++){ x=read();y=read();z=read(); g[x].push_back(make_pair(y,z)); g[y].push_back(make_pair(x,z)); } dfs(1,-1); printf("%d ",f[1][m]); return 0; }
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; #define N 16050 inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } int f[N]; int n,ans; vector< int >g[N]; void dfs(int x,int fa){ for(int i=0;i<g[x].size();i++){ int y=g[x][i]; if(y==fa)continue; dfs(y,x); f[x]+=max(f[y],0); } ans=max(ans,f[x]); } int main(){ n=read(); for(int i=1;i<=n;i++)f[i]=read(); for(int i=1,x,y;i<n;i++){ x=read();y=read(); g[x].push_back(y); g[y].push_back(x); } dfs(1,0); printf("%d ",ans); return 0; }
#include<iostream> #include<cstdio> #include<vector> using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } const int N = 2000; int n,ans,f[N][2]; vector< int >g[N]; bool vis[N]; void dfs(int x,int fa){ f[x][1]=1;f[x][0]=0; for(int i=0;i<g[x].size();i++){ int y=g[x][i]; if(y==fa)continue; dfs(y,x); f[x][0]+=f[y][1]; f[x][1]+=min(f[y][1],f[y][0]); } } int main(){ n=read(); for(int i=1,x,y,num;i<=n;i++){ x=read();num=read(); while(num--){ y=read(); g[x].push_back(y); g[y].push_back(x); } } dfs(0,-1); printf("%d",min(f[0][0],f[0][1])); return 0; }