P3080 [USACO13MAR] The Cow Run G/S

Farmer John has forgotten to repair a hole in the fence on his farm, and his N cows (1

无

无

Four cows placed in positions: -2, -12, 3, and 7. The optimal visit order is -2, 3, 7, -12. FJ arrives at position -2 in 2 minutes for a total of 2 dollars in damage for that cow. He then travels to position 3 (distance: 5) where the cumulative damage is 2 + 5 = 7 dollars for that cow. He spends 4 more minutes to get to 7 at a cost of 7 + 4 = 11 dollars for that cow. Finally, he spends 19 minutes to go to -12 with a cost of 11 + 19 = 30 dollars. The total damage is 2 + 7 + 11 + 30 = 50 dollars.