Transportation | Topcoder Archive

Problem Statement

You need to transport n packages numbered from 0 to n - 1. To transport packages you can rent a truck. Renting a truck to transport k packages costs a + k^2 dollars. The capacity of a truck is limited, so each truck can only transport packages with a total weight of at most c. You may need to rent a truck several times to transport all packages. Packages are ordered by their priority, so packages with smaller numbers must be transported no later than packages with larger numbers.

You are given a int[] w, the i-th element of which is the weight of the i-th package. Return the minimal total cost of transporting the packages.

Definition

Class:: Transportation
Method:: minCost
Parameters:: int[], int, int
Returns:: int
Method signature:: int minCost(int[] w, int c, int a)
(be sure your method is public)

Constraints

w will contain between 1 and 50 elements, inclusive.
c will be between 1 and 50,000, inclusive.
Each element of w will be between 1 and c, inclusive.
a will be between 1 and 1000, inclusive.

Examples

```
{2,3,4,2}
```
```
5
```
```
4
```
```
Returns: 18
```
You must transport packages 0 and 1 together for 4 + 2^2 = 8 dollars, and transport separately packages 2 and 3 each for 4 + 1^2 = 5 dollars.
```
{2,3,4,2}
```
```
4
```
```
1
```
```
Returns: 8
```
This time it is cheaper to transport each package separately, for 1 + 1^2 = 2 dollars.
```
{2,3,4,2}
```
```
20
```
```
1
```
```
Returns: 8
```
The truck is big, but it is still cheaper to transport each package separately.
```
{2,3,4,2}
```
```
20
```
```
10
```
```
Returns: 26
```
This time it is cheaper to transport all packages together.
```
{1,2,1,2}
```
```
2
```
```
10
```
```
Returns: 44
```
It is impossible to transport packages 0 and 2 together because package 1 cannot be transported before package 0, nor it can be transported after package 2.

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.