You have a one-dimensional array of pixels. Each pixel has a value, represented by a number between 0 and 255, inclusive. The distance between two pixels is the absolute difference of their numbers.
You can perform each of the following operations zero or more times:
- With cost , delete any pixel, so its original neighbors become neighboring pixels.
- With cost , insert one pixel of any value into any position -- either between two existing pixels, or before the first pixel, or after the last pixel.
- You can change the value of any pixel. The cost is the absolute difference of the old value of the pixel and the new value of the pixel.
The array is smooth if any neighboring pixels have distance at most . Find the minimum possible cost of a sequence of operations that makes the array smooth.
Note: The empty array -- the array containing no pixels -- is considered to be smooth.
Input Specification
The first line of the input gives the number of test cases, . test cases follow, each with two lines. The first line is in the form "", the next line contains numbers : the values of the pixels from left to the right.
Output Specification
For each test case, output one line containing Case #x: y
, where is the case number (starting from 1), and is the minimum cost to make the input array smooth.
Limits
Time limit: 30 seconds per test set.
Memory limit: 1 GB.
All the numbers in the input are integers.
Small Dataset
.
Large Dataset
.
Sample Input
2
6 6 2 3
1 7 5
100 1 5 3
1 50 7
Sample Output
Case #1: 4
Case #2: 17
Explanation for Sample
In Case #1, decreasing the 7 to 3 costs 4 and is the cheapest solution. In Case #2, deleting is extremely expensive; it's cheaper to insert elements so your final array looks like [1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 50, 45, 40, 35, 30, 25, 20, 15, 10, 7]
.
Comments