A Binary Apple Tree
Time Limit: 1.0 second
Memory Limit: 16 MB
Let's
imagine how apple tree looks in binary computer world. You're right, it
looks just like a binary tree, i.e. any biparous branch splits up to
exactly two new branches. We will enumerate by natural numbers the root
of binary apple tree, points of branching and the ends of twigs. This
way we may distinguish different branches by their ending points. We
will assume that root of tree always is numbered by 1 and all numbers
used for enumerating are numbered in range from 1 to N, where N is the total number of all enumerated points. For instance in the picture below N is equal to 5. Here is an example of an enumerated tree with four branches:
As
you may know it's not convenient to pick an apples from a tree when
there are too much of branches. That's why some of them should be
removed from a tree. But you are interested in removing branches in the
way of minimal loss of apples.
So your are given amounts of apples on a branches and amount of
branches that should be preserved. Your task is to determine how many
apples can remain on a tree after removing of excessive branches.
Input
First line of input contains two numbers: N and Q (1 ≤ Q ≤ N; 1 < N ≤ 100). N denotes the number of enumerated points in a tree. Q denotes amount of branches that should be preserved. Next N−1
lines contains descriptions of branches. Each description consists of a
three integer numbers divided by spaces. The first two of them define
branch by it's ending points. The third number defines the number of
apples on this branch. You may assume that no branch contains more than
30000 apples.
Output
Output should contain the only number — amount of apples that can be preserved. And don't forget to preserve tree's root ;-)
Sample
| input |
output |
5 2
1 3 1
1 4 10
2 3 20
3 5 20
|
21
|
簡析:
這是一個簡單的樹形動態規劃問題,大概可以拿來當這類題目的入門訓練題.雖然這是URAL上的第一個樹形DP,但是我奇怪的是它的通過率并不很高.
對于原題目的圖形,用數組value[a][b]表示a,b點間蘋果的個數,用nd[p].L,nd[p].R分別表示節點p的左右兒子.通過build_tree(1)獲得數組nd[],從而獲得整棵樹的信息.
接著,用ans[p][i]表示
以節點p為祖宗的子樹,保留的枝條不超過i條時所能保留的最多的蘋果,狀態轉移有一下幾種情況.
在除去多余枝條的后的圖中,
1.
p只與一個兒子相連: ans[p][i]=max(ans[left_son][i-1]+value[left_son][p],ans[right_son][i-1]+value[right_son][p]);
2.
p與兩個兒子相連: for (int j=0;j<=i-2;++j)
ans[p][i]=max(ans[p][i],ans[left_son][j]+ans[right_son][i-j-2]+d);
這里,d=value[left_son][p]+value[right_son][p];
算法在o(N*Q*Q)級別
1 #include<iostream>
2 using namespace std;
3 const int MAXN=102;
4 int n,q,value[MAXN][MAXN],ans[MAXN][MAXN];
5 struct node
6 {
7 int l,r;
8 }nd[MAXN];
9
10 void build_tree(int p)
11 {
12 int flg=0;
13 for (int i=1;i<=n;++i)
14 if (value[p][i] && (!nd[i].l))
15 {
16 flg=1;
17 if (nd[p].l==0) nd[p].l=i;
18 else
19 {nd[p].r=i; break;}
20 }
21 if (!flg) return;
22 if (nd[p].l) build_tree(nd[p].l);
23 if (nd[p].r) build_tree(nd[p].r);
24 }
25
26 void calc(int p)
27 {
28 if (!nd[p].l) return;
29 int l=nd[p].l,r=nd[p].r;
30 calc(l);
31 calc(r);
32 ans[p][1]=max(value[l][p],value[r][p]);
33
34 int d=value[l][p]+value[r][p];
35 for (int i=2;i<=q;++i)
36 {
37 ans[p][i]=max(ans[l][i-1]+value[l][p],ans[r][i-1]+value[r][p]);
38 for (int j=0;j<=i-2;++j)
39 ans[p][i]=max(ans[p][i],ans[l][j]+ans[r][i-j-2]+d);
40 }
41 }
42
43
44 int main()
45 {
46 //freopen("data.in","r",stdin);
47 //freopen("data.out","w",stdout);
48 cin >> n >> q;
49 memset(value,0,sizeof(value));
50 for (int i=1;i<n;++i)
51 {
52 int a,b,c;
53 cin >> a >> b >> c;
54 value[a][b]=c;
55 value[b][a]=c;
56 }
57 memset(nd,0,sizeof(nd));
58 build_tree(1);
59 calc(1);
60 cout << ans[1][q] << endl;
61 return 0;
62 }
63