PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
We present two important observations of the problem:
- The corresponding graph is a tree, because it is connected and has N-1 edges.
- After we move a chef from city a to city b, it is useless to move it to city a again.
Those observations make the problem possible to be solved using DP in tree. To simplify the DP, we first transform the tree into child-sibling representation rooted at node 1. Let DP(n, c, d) be the maximum profit achieved in the subtree rooted at the parent[n], with c chefs available in parent[n], and we are given d days remaining. The recurrence is given in this pseudocode:
DP(n, c, d) = max (
DP(sibling[n], c, d), // doesn’t transfer any chefs from parent[n] to n
max ({DP(child[n], rc, rd) + DP(sibling[n], c - rc, d - 1 - rd) : 1 <= rc <= c and 0 <= rd <= d - 1}) // transfers rc chefs to n and gives rd days
)
The base case is when n is null (sentinel node that is the sibling of the last sibling of a node). We can build a restaurant in parent[n] if c and d are positive, and also if S[parent[n]] is not negative. So, DP(n, c, d) = max(0, S[parent[n]]) if n is sentinel node and c and d are positive.
The solution to the problem is then available in DP(child1, C, D). We can then use all information in the DP table to reconstruct an optimal expansion plan.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.