RoadOrFlightEasy | Topcoder Archive

Problem Statement

The king has been out to work for a long time and he wants to go back to his queen as fast as possible. The king is in city 0 and the queen is in city N. There are roads and flights connecting city i to city (i+1) for all i between 0 and N-1, inclusive.

You are given int[] roadTime whose i-th element is the time it takes to travel from city i to city (i+1) by road and int[] flightTime whose i-th element is the time it takes to travel from city i to city (i+1) by flight. However, taking a flight risks the life of the king due to the technological limitations in the kingdom. Hence the queen has asked the king to take at most K flights on his way.

Return the minimum amount of time in which the king can reach his queen.

Definition

Class:: RoadOrFlightEasy
Method:: minTime
Parameters:: int, int[], int[], int
Returns:: int
Method signature:: int minTime(int N, int[] roadTime, int[] flightTime, int K)
(be sure your method is public)

Constraints

N will be between 1 and 50, inclusive.
roadTime will contain exactly N elements.
flightTime will contain exactly N elements.
Each element of roadTime and flightTime will be between 1 and 1000, inclusive.
K will be between 0 and N, inclusive.

Examples

```
3
```
```
{4, 6, 7}
```
```
{1, 2, 3}
```
```
1
```
```
Returns: 13
```
All flightTimes here are less than roadTimes. However the king can choose only 1 flight. The are two possible optimal routes. City 0-->1, 1-->2 by road and 2-->3 by flight takes time 4 + 6 + 3 = 13 units. City 0-->1 by road, 1-->2 by flight and 2-->3 by road also takes time 4 + 2 + 7 = 13 units.
```
3
```
```
{4, 6, 7}
```
```
{1, 2, 3}
```
```
2
```
```
Returns: 9
```
Now the king is allowed to take 2 flights.
```
3
```
```
{4, 6, 7}
```
```
{1, 2, 3}
```
```
3
```
```
Returns: 6
```
Choose all 3 flights since flights are faster than roads.
```
3
```
```
{1, 2, 3}
```
```
{2, 3, 4}
```
```
2
```
```
Returns: 6
```
flightTime can be larger than roadTime. So the King may take fewer than K flights even though he is allowed to take K of them.

{50, 287, 621, 266, 224, 68, 636}

{797, 661, 644, 102, 114, 452, 420}

Returns: 1772

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.