企业网站优化的弊端,各国网站域名,阿里云免费服务器领取,口碑好的聊城网站建设Description 探险队长凯因意外的弄到了一份黑暗森林的藏宝图#xff0c;于是#xff0c;探险队一行人便踏上了寻宝之旅#xff0c;去寻找传说中的宝藏。藏宝点分布在黑暗森林的各处#xff0c;每个点有一个值#xff0c;表示藏宝的价值。它们之间由一些小路相连#xff0…Description 探险队长凯因意外的弄到了一份黑暗森林的藏宝图于是探险队一行人便踏上了寻宝之旅去寻找传说中的宝藏。藏宝点分布在黑暗森林的各处每个点有一个值表示藏宝的价值。它们之间由一些小路相连小路不会形成环即两个宝藏点之间有且只有一条通路。探险队从其中的一点出发每次他们可以留一个人在此点开采宝藏也可以不留然后其余的人可以分成若干队向这一点相邻的点走去。需要注意的是如果他们把队伍分成两队或两队以上就必须留一个人在当前点提供联络和通讯当然这个人也可以一边开采此地的宝藏。并且为了节约时间队伍在前往开采宝藏的过程中是不会走回头路的。现在你作为队长的助理已经提供了这幅藏宝图请你算出探险队所能开采的最大宝藏的价值。 Input 第一行有两个正整数n(1n100)表示藏宝点的个数m(1m100)表示探险队的人数。第二行是n个不超过100的正整数分别表示1到n每个点的宝藏价值。接下来的n-1行每行两个数x和y(1x,yn,xy)表示藏宝点x,y之间有一条路数据保证不会有重复的路出现。假设一开始探险队在点1处。 Output 一个整数表示探险队所能获得最大的宝藏价值。 Sample Input 5 3
1 3 7 2 8
1 2
2 3
1 4
4 5 题解 又是一道树形dp今天题做的要死了题目说 它们之间由一些小路相连小路不会形成环即两个宝藏点之间有且只有一条通路 显然就是棵树容易得到设f[i][j]以i为根的子树剩j的的最大价值那就有两种情况①当前点不挖直接跳②当前点留一个人挖可以向下派j-1个人则有 f[i][j]max(f[i][j]f[i][j-1-k]f[son[i]][k]v[i]) 那么我们不知道在f[i][j-1-k]中是否有v[i]如果有就算重了 可以多定一个数组g也可以多加一维其实是一样的 g[i][j]表示 ]以i为根的子树剩j不挖i 的的最大价值 代码 1 #includecstdio2 #includeiostream3 #includealgorithm4 using namespace std;5 int n,m,cnt,v[110],f[110][110],to[210],from[210],head[110],k[110],g[110][110];6 void insert(int x,int y) { to[cnt]y; from[cnt]head[x]; head[x]cnt; }7 void dp(int root,int fa)8 {9 f[root][1]v[root];
10 for (int whead[root];w;wfrom[w])
11 if (to[w]!fa)
12 {
13 dp(to[w],root);
14 for (int i1;im;i) k[i]max(f[root][i],f[to[w]][i]);
15 for (int i1;im;i)
16 for (int j1;ji;j)
17 k[i]max(k[i],g[root][i-j-1]f[to[w]][j]v[root]);
18 for (int i1;im;i) f[root][i]k[i];
19 for (int i1;im;i) k[i]max(f[to[w]][i],g[root][i]);
20 for (int i1;im;i)
21 for (int j1;ji;j)
22 k[i]max(k[i],g[root][i-j]f[to[w]][j]);
23 for (int i1;im;i) g[root][i]k[i];
24 }
25 }
26 int main()
27 {
28 scanf(%d%d,n,m);
29 for (int i1;in;i) scanf(%d,v[i]);
30 for (int i1;in-1;i)
31 {
32 int x,y;
33 scanf(%d%d,x,y);
34 insert(x,y); insert(y,x);
35 }
36 dp(1,0);
37 printf(%d,f[1][m]);
38 return 0;
39 } 转载于:https://www.cnblogs.com/Comfortable/p/9277479.html
