DancingLessons | Topcoder Archive

Problem Statement

To prepare for a dancing contest, you must attend k lessons.

There is one dancing lesson per day available for the following n days. To go to the lesson on the i-th day you must attend at least a[i] of the previous lessons. Attending the lesson on the i-th day costs cost[i].

Return the minimal amount you must pay to prepare for the contest. If it is impossible to prepare for the contest, return -1.

Definition

Class:: DancingLessons
Method:: minCost
Parameters:: int[], int[], int
Returns:: int
Method signature:: int minCost(int[] a, int[] cost, int k)
(be sure your method is public)

Constraints

a will contain between 1 and 50 elements, inclusive.
Each element of a will be between 0 and 50, inclusive.
cost will contain the same number of elements as a.
Each element of cost will be between 1 and 1000, inclusive.
k will be between 1 and 50, inclusive.

Examples

```
{1,0,1}
```
```
{2,1,3}
```
```
2
```
```
Returns: 4
```
You must attend two lessons. You cannot attend the lesson on day 0 because it is required that you attend at least one lesson before it. So you attend lessons on days 1 and 2 for a total cost of 1 + 3 = 4.
```
{0,1,0,1}
```
```
{5,2,1,8}
```
```
2
```
```
Returns: 6
```
It is best to attend lessons on day 0 and day 2.
```
{1}
```
```
{10}
```
```
1
```
```
Returns: -1
```
There is one lesson, but you cannot attend it because it is required to attend one lesson before.
```
{1,0,1,0,1}
```
```
{1,2,3,2,1}
```
```
3
```
```
Returns: 5
```
```
{0}
```
```
{1}
```
```
50
```
```
Returns: -1
```

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.