KiAsaGibona's blog

DP Problem SPOJ (classical-1482) Help Please

By KiAsaGibona, 10 years ago, In English

Hi, this link refers to a Nice Dynamic Programming Problem . I am thinking how to solve this problem but haven't found any good one. Any suggestion on this problem will be a great hand.

And for future references, I ask you to provide link of this kind of problems. And also if you provide some tutorial of this kind of problems that would be great. :)

Thank you all.. Have a nice day :)

alternate link for this problem

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

Consider any node as the root of the tree.

Let A[i]= minimum number of tickets for subtree rooted at node i and B[i]= minimum number of tickets for subtree rooted at node i where node i can be connected to at most one node.

Note that B[i]>=A[i].

for every node i, use dp to calculate A[j] and B[j] for all children j of i. Now We can calculate A[i] and B[i] as follows: There can be at most 3 cases.

  1. node i is not connected to any node, so A[i]= 1+ sum(A[j]);
  2. node i is connected to one node. Let x be the child of i whose B[j]-A[j] is minimum. Then we connect this child with i. So A[i]=sum(a[j])-A[x]+B[x];
  3. node i is connected to two nodes. Then take two child x and y whose B[j]-A[j] is minimum. It is like the previous one . A[i]= sum(a[j])-A[x]+B[x]-A[y]+B[y]-1; Just take the minimum of this three results.

B[i] can be computed in similar way.

→ Reply