P2589 [ZJOI2006] Stacking Bowls

Xiao H has $n$ bowls to put into a cupboard. She wants to stack them. Each bowl is a right circular frustum (wider at the top and narrower at the bottom). You have measured each bowl’s two radii and height. Please help Xiao H find a stacking order that minimizes the total height of the stack. For example: 

The first line contains an integer $n$, the number of bowls. Each of the next $n$ lines contains three integers $h$, $r_1$, $r_2$, denoting the bowl’s height and its two radii, where $r_1 < r_2$.

Output a single number, the minimal height, rounded to the nearest integer.

Constraints: 100% of the testdata satisfies $n \le 9$. The absolute value of every input number does not exceed 1000. Translated by ChatGPT 5