Please, help me find the problem

Revision en1, by AbsurdMan, 2024-04-30 21:15:52

I remember a problem called "lighthouses". It was something like the following:

There are $$$n$$$ lighthouses on a circle. Given distances between each pair of lighthouses, you need to find a continuous path through them of minimal cost. No two segments of your path can intersect.

It had a $$$O(n^3)$$$ dp solution and I don't remember where I heard it. Perhaps from an ICPC contest? Do you know what problem am I talking about?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English AbsurdMan 2024-04-30 21:15:52 459 Initial revision (published)