Indian Computing Olympiad

Dynamic programming on trees→Catering contracts

We have a railway network with no cycles with expected profit at each station. Contractors bid for a subset of stations to maximize profit. A caterer may not bid for two adjacent stations. What is the best way to pick the stations?

For instance, here is a network:

       10                    20
         \                  /
          30--------------40
         /                  \
       20                    30
      

In this case, the best choice are the outer four nodes with value 10+20+20+30 = 80.

Solution

---