Dynamic Programming Practice 3
Mike starts at stone \(1\) and wishes to reach stone \(N\). Mike can jump up to \(K\) stones forward. Each stone \(i\) has a height \(h_{i}\). The cost for jumping between stones \(i\) and \(j\) is \(|h_{i} - h_{j}|\). Some of the stones are magical. Jumping on a magical stone incurs an additional cost of \(P\), the number of magical stones previously visited. Help Mike find the minimum cost required to reach stone \(N\).
Constraints
\(1 \leq N, K \leq 300\)
\(1 \leq h_{i} \leq 10^{3}\)
Input Specification
The first line contains two integers \(N\) and \(K\).
The second line contains \(N\) integers, \(h_{i}\).
The third line contains \(N\) integers, \(1\) if stone \(i\) is magical and \(0\) if not.
Output Specification
Output one integer, the minimum cost.
Sample Input
5 2
1 3 3 2 3
1 0 1 0 1Sample Output
5Explanation for Sample Output
An optimal path is through stones \(1\), \(2\), \(4\), and \(5\). This incurs a cost of \(|h_1 - h_2| + |h_2 - h_4| + |h_4 - h_5| + 1 = |1 - 3| + |3 - 2| + |2 - 3| + 1 = 2 + 1 + 1 + 1 = 5\). Another possible path would be through stones \(1\), \(3\), and \(5\), which also incurs a cost of 5.
Comments
You spelt explanation wrong ๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐๐
also the path through 1, 3, 5 is more optimal no??
|1-3| + |3-3| + 1 + 1 = 4
"Jumping on a magical stone incurs an additional cost of, the number of magical stones previously visited." If you jump onto a second magical stone your incurred cost is 2, not 1. In the case 1,3,5 the incurred cost would be |1-3| + |3-3| + 1 + 2 = 5. Please read the problem statement more carefully in the future.