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?