BobTheBuilder | Topcoder Archive

Problem Statement

Bob The Builder has N boxes. Each box has a happiness level. Let A[0],A[1],....A[N - 1] be the cost of N boxes. Bob wants to make beautiful box towers using all the boxes. A box tower is formed by putting boxes one above the other. And a tower is beautiful only if every boxâs happiness divides happiness value of each of the boxes above it. Bob can make any number of towers. The cost of making a tower is the maximum box happiness present in the tower.

Help Bob by calculating the minimum cost required to form towers using all the boxes.

Definition

Class:: BobTheBuilder
Method:: minimumCost
Parameters:: int, int[]
Returns:: long
Method signature:: long minimumCost(int N, int[] A)
(be sure your method is public)

Constraints

The number of boxes, N is between 1 and 400 (inclusive).
The happiness level of boxes, Ai is between 1 and 109 (inclusive).

Examples

```
4
```
```
{9,12,24,36}
```
```
Returns: 60
```
We can make 2 towers as follows : The first tower consisting of numbers {36, 9} and the second tower of numbers {24, 12}. So the total cost is 36 + 24 = 60.

{4772645,33887245,3896612,2973,2913,16127339,4714205,1954,974069,971}

Returns: 64379955

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.