二叉苹果树：https://ac.nowcoder.com/acm/problem/50505
有一棵二叉苹果树，如果数字有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共N个节点，标号1至N，树根编号一定为1。
我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。
输入
5 2 1 3 1 1 4 10 2 3 20 3 5 20
输出
21
代码：
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<sstream> #include<vector> #include<stack> #include<deque> #include<cmath> #include<map> #include<queue> #include<bitset> //#include<hash_map> #define sd(x) scanf("%d",&x) #define lsd(x) scanf("%lld",&x) #define ms(x,y) memset(x,y,sizeof x) #define fu(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) #define all(a) a.begin(),a.end() #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; //using namespace __gnu_cxx; typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int maxn=1e2+79; const int mod=998244353; const int INF=1e9+7; const double pi=acos(-1); ll dp[maxn][maxn],a[maxn]; vector<od> son[maxn]; int n,k; void dfs(int x,int fa) { for(od y:son[x]) { int nxt=y.to,len=y.len; if(nxt==fa) continue; dfs(nxt,x); //dp:第i个点为根，连着j条根 fd(j,k,1) { fu(t,0,j-1) //左+右组合 dp[x][j]=max(dp[nxt][t]+dp[x][j-t-1]+len,dp[x][j]); } } } int main() { sd(n);sd(k); fu(i,1,n-1) { int u,v,w;sd(u);sd(v);sd(w); son[u].push_back(od{v,w}); son[v].push_back(od{u,w}); } dfs(1,0); int ans=dp[1][k]; printf("%lld\n",ans); return 0; }
选课：https://ac.nowcoder.com/acm/problem/51179
学校实行学分制。
每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。
学校开设了 N 门的选修课程，每个学生可选课程的数量 M 是给定的。
学生选修了这 M 门课并考核通过就能获得相应的学分。
在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其他的一些课程的基础上才能选修。
例如《Windows程序设计》必须在选修了《Windows操作基础》之后才能选修。
我们称《Windows操作基础》是《Windows程序设计》的先修课。
每门课的直接先修课最多只有一门。
两门课可能存在相同的先修课。
你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修条件。
假定课程之间不存在时间上的冲突。
每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。
学校开设了 N 门的选修课程，每个学生可选课程的数量 M 是给定的。
学生选修了这 M 门课并考核通过就能获得相应的学分。
在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其他的一些课程的基础上才能选修。
例如《Windows程序设计》必须在选修了《Windows操作基础》之后才能选修。
我们称《Windows操作基础》是《Windows程序设计》的先修课。
每门课的直接先修课最多只有一门。
两门课可能存在相同的先修课。
你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修条件。
假定课程之间不存在时间上的冲突。
输入描述：
输入文件的第一行包括两个整数N、M（中间用一个空格隔开）其中1≤N≤300,1≤M≤N,1≤N≤300,1≤M≤N
接下来N行每行代表一门课，课号依次为1，2，…，N。
每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。
学分是不超过10的正整数。
每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。
学分是不超过10的正整数。
输入：
7 4
2 2 0 1 0 4 2 1 7 1 7 6 2 2
输出：
13
代码：
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<sstream> #include<vector> #include<stack> #include<deque> #include<cmath> #include<map> #include<queue> #include<bitset> //#include<hash_map> #define sd(x) scanf("%d",&x) #define lsd(x) scanf("%lld",&x) #define ms(x,y) memset(x,y,sizeof x) #define fu(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) #define all(a) a.begin(),a.end() #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; //using namespace __gnu_cxx; typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int maxn=300+79; const int mod=998244353; const ll INF=0x7f7f7f7f; const double pi=acos(-1); ll dp[maxn][maxn],sco[maxn]; vector<int> to[maxn]; int n,m; void dfs(int x) { dp[x][0]=0; if(!to[x].empty()) { for(int y:to[x]) { dfs(y); fd(j,m,0) //总共选j个,01背包倒序 fu(k,0,m) if(j-k>=0) dp[x][j]=max(dp[x][j],dp[x][k]+dp[y][j-k]); } } if(x!=0)//不是0的话，都要加上x点的学分 fd(i,m,1) dp[x][i]=dp[x][i-1]+sco[x]; } int main() { sd(n);sd(m); fu(i,1,n) { int x,score; sd(x);sd(score); sco[i]=score; to[x].push_back(i); } //建一个超级点0 dfs(0); printf("%lld\n",dp[0][m]); return 0; }
Note:
两题都是树上背包。两题f[u][j]都是表示以u为根，选j个边（点）的最优解。
第一题：选边使边权和最小。
• f[u][j] = max(f[u][k] + f[v][j – k - 1] + W)
• v分别是u的儿子，w为u到v边上的苹果数目（也即这条边权值）, k属于[0, j]。
第二题：选点使点权最大。
• f[u][j] = max(f[u][k] + f[v][j – k ])
• v分别是u的儿子， k属于[0, j]。
•最后（因为以x为根，点x一定要选上）
//把每个点x的学分都加上去,逆序是为了让一个点的值不被重复加上去 for(int i=m;i>=1;i--) dp[x][i]=dp[x][i-1]+val[x];