洛谷2015二叉苹果树

题目描述

有一棵苹果树,如果树枝有分叉,一定是分2叉(就是说没有只有1个儿子的结点)

这棵树共有N个结点(叶子点或者树枝分叉点),编号为1-N,树根编号一定是1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树

2   5
 \ / 
  3   4
   \ /
    1

现在这颗树枝条太多了,需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量,求出最多能留住多少苹果。

输入输出格式

输入格式:

 

第1行2个数,N和Q(1<=Q<= N,1<N<=100)。

N表示树的结点数,Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。

每行3个整数,前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。

每根树枝上的苹果不超过30000个。

 

输出格式:

 

一个数,最多能留住的苹果的数量。

 

输入输出样例

输入样例#1: 复制
5 2
1 3 1
1 4 10
2 3 20
3 5 20
输出样例#1: 复制
21

***这是一个由根分成左子树和右子树两部分的情况的树型DP
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 int i,j,n,q,l[105],r[105],f[105][105] = {0},map[105][105],a[105];//f[i][j]代表以i为节点保留j个节点的最大权值和 
 7 void buildtree(int v) //建树
 8 {
 9     for(int i = 1;i <= n;i++)
10     {
11         if(map[v][i] >= 0)      //左子树 
12         {
13             l[v] = i;
14             a[i] = map[v][i];
15             map[v][i] = -1;
16             map[i][v]= map[v][i];  //标记访问 
17             buildtree(i);
18             break;
19         }
20      }
21      for(i = 1;i <= n;i++)
22      {
23          if(map[v][i] >= 0) //右子树 
24          {
25              r[v] = i;
26              a[i] = map[v][i];
27              map[v][i] = -1;
28              map[i][v] = map[v][i];  //标记访问 
29              buildtree(i);
30              break;
31          }
32       } 
33  }
34 int DP(int i,int j) //树型DP,记忆化搜索 
35 {
36     if(j == 0)
37     return 0;
38     if((l[i] == 0) && (r[i] == 0))
39     return a[i]; // 叶子节点
40     if(f[i][j] > 0)
41     return f[i][j]; // 已经计算
42     for(int k = 0;k <= j - 1;k++)
43     {
44         f[i][j] = max(f[i][j],DP(l[i],k) + DP(r[i],j - k - 1) + a[i]);
45     }
46     return f[i][j];
47  } 
48 int main()
49 {
50     int x,y,z;
51     scanf("%d %d",&n,&q);
52     q = q + 1;
53     for(i = 1;i <= n;i++)
54     {
55         for(j = 1;j <= n;j++)
56         {
57             map[i][j] = -1;
58         }
59     }
60     for(i = 1;i <= n - 1;i++)
61     {
62         scanf("%d %d %d",&x,&y,&z);
63         map[x][y] = z;
64         map[y][x] = map[x][y]; 
65     }
66     buildtree(1); // 以1为根建立二叉树
67     printf("%d",DP(1,q));
68     return 0;
69 }

 

 

洛谷2015二叉苹果树

上一篇:Office Excel 一键抓取网页表格数据


下一篇:手机隐藏ip地址的方法简单设置