Hi everyone. Today i meet a problem like that: There are n cities, and each city i has a height h_i and a rental cost p_i for using a flying vehicle. To travel from city i to city j, the cost is defined as: cost(i, j) = max(p_i, h_j — h_i).
A tourist wants to start from city 1, visit all cities exactly once, and finally return to city 1, using the flying vehicle. Your task is to determine the minimum total travel cost.
Input: • The first line contains an integer n (1 ≤ n ≤ 10⁵) — the number of cities. • Each of the next n lines contains two integers h_i and p_i (0 ≤ h_i, p_i ≤ 10⁹) — the height and the rental cost of city i.
Output: • Output a single integer — the minimum total cost to visit all cities exactly once, starting and ending at city 1.
I think it maybe a dp problem. I guess suppose you have solution for n-1, if you add n to path, it will add destroy the structure of the path in n-1 before. Example if you have 1-3-5-4-2-1 is the answer of n=5, if you add 6 to the path 6 may be between 1,3 or 3,5 or 5,4 ... Is it right solution or someone has others answer. Thank you for your help.
cost is $$$\sum_{i=1}^{n}p_i$$$ plus some additional cost. So we want to minimize the additional cost. Sort everything by height. if we are at $$$h_i$$$, and want to go to $$$h_j$$$, the cost is 0 if $$$h_j \lt h_i + p_i$$$ and $$$h_j-h_i-p_i$$$ otherwise. Note that going down is always free. We do dp to get the minimum extra cost to be at height $$$h_i$$$. Either this value depends linearly on some previous value (as in $$$C + h_j$$$ for some C), or it is constant (if it is close enough to some previous height). We of course take the minimum of these 2 options. Maintain a data structure to update the minimum (C) in some interval, and query at a point (segment tree). Complexity is $$$O(n\log(n))$$$ with coordinate compression.
Thank you so much for your help
Is the cost of the last trip always equal to p_i? If so, this is the key to the solution.
Yes pi it seem the key of the problem. I think use pi and greedy to tackle this problem still okay for this problem
We cannot pay less than p_i. Our goal is to try not to pay more. I think the optimal sequence would be as follows: from the starting city, go in ascending order of height. From the highest city, move to the city below the starting city, go down, and then return to the starting city at a fixed cost.
That right. It is all my thinking about this problem also
There is another strategy that may be optimal: from the starting city, we go straight to the highest city, and then we only go down. Apparently, we need to calculate the results for both strategies and choose the optimal one.
It's probably dp after all. Our task is to get to the highest city with minimal extra cost. We have to check all the possibilities. Here's my attempt to implement it.