教育行业展示网站模板,国际知名平面设计网站,网站字体变大代码,建英语网站首页P2015 二叉苹果树 类似于带限制背包问题#xff0c;但不知道也能做。 n , q n,q n,q 范围小#xff0c;大胆设 dp 状态。设 f u , i \large f_{u,i} fu,i 表示 u u u 子树内保留 i i i 根树枝的最大苹果数#xff0c;可得状态转移方程 f u , i f u , j f v , i − …P2015 二叉苹果树 类似于带限制背包问题但不知道也能做。 n , q n,q n,q 范围小大胆设 dp 状态。设 f u , i \large f_{u,i} fu,i 表示 u u u 子树内保留 i i i 根树枝的最大苹果数可得状态转移方程 f u , i f u , j f v , i − j − 1 w \large f_{u,i}f_{u,j}f_{v,i-j-1}w fu,ifu,jfv,i−j−1w其中 w w w 指连接 u , v u,v u,v 的树枝上的苹果数 i − j − 1 i-j-1 i−j−1 而非 i − j i-j i−j 在于 u , v {u,v} u,v 这条边占了一根树枝。注意此时的 f u , j f_{u,j} fu,j 不能包含当前 v v v 所在的子树原因很显然同一个子树上的树枝不能被计算两次。
列完转移方程注意边界和外层循环。边界 f u . 0 0 f_{u.0}0 fu.00因为转移时 f u , i f_{u,i} fu,i 调用的 f u , j f_{u,j} fu,j 不能包含当前 v v v 所在的子树所以应将 i i i 从大到小转移。
时间复杂度 O ( n q 2 ) O(nq^2) O(nq2)。
在这里插入代码片#includebits/stdc.h
using namespace std;
int n,q,p[105],f[105][105];
struct qh{int v,w,nt;
}E[205];
void add(int u,int v,int w){E[p[0]](qh){v,w,p[u]};p[u]p[0];return ;}
void dfs(int u,int fa){for(int ip[u];i;iE[i].nt){int vE[i].v;if(vfa) continue;dfs(v,u);for(int jq;j1;j--) for(int k0;kj-1;k) f[u][j]max(f[u][j],f[u][k]f[v][j-k-1]E[i].w);}return ;
}
int main(){scanf(%d%d,n,q);for(int i1;in;i){int u,v,w;scanf(%d%d%d,u,v,w);add(u,v,w);add(v,u,w);}dfs(1,0);printf(%d,f[1][q]);return 0;
}
/*
start coding:18:47
finish debuging:19:03
*/附上题目
二叉苹果树
题目描述
有一棵苹果树如果树枝有分叉一定是分二叉就是说没有只有一个儿子的结点
这棵树共有 N N N 个结点叶子点或者树枝分叉点编号为 1 ∼ N 1 \sim N 1∼N树根编号一定是 1 1 1。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 4 4 4 个树枝的树
2 5\ / 3 4\ /1现在这颗树枝条太多了需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量求出最多能留住多少苹果。
输入格式
第一行 2 2 2 个整数 N N N 和 Q Q Q分别表示表示树的结点数和要保留的树枝数量。
接下来 N − 1 N-1 N−1 行每行 3 3 3 个整数描述一根树枝的信息前 2 2 2 个数是它连接的结点的编号第 3 3 3 个数是这根树枝上苹果的数量。
输出格式
一个数最多能留住的苹果的数量。
样例 #1
样例输入 #1
5 2
1 3 1
1 4 10
2 3 20
3 5 20样例输出 #1
21提示 1 ⩽ Q N ⩽ 100 1 \leqslant Q N \leqslant 100 1⩽QN⩽100每根树枝上的苹果 ⩽ 3 × 1 0 4 \leqslant 3 \times 10^4 ⩽3×104。
