Wedding Procession
Time limit2sMemory limit128 MB
Arrange all guests in a line minimizing the sum of adjacent height differences while keeping the given lion subsequence order fixed.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Greedy, Sorting
- Solved
- No attempts yet
Problem
Today is a joyful wedding day for an ant and an elephant. The guests will celebrate by making a train procession: everyone stands in one line, and each person places their hands on the shoulders of the person in front. The procession looks less beautiful when adjacent people have very different heights.
The beauty of the procession is measured by the sum of the height differences of every adjacent pair. The smaller this sum is, the more beautiful the procession is.
There is one restriction. The lion family has a strict hierarchy. The lions are given in order from highest rank to lowest rank, and their order in the procession must not be reversed. All other guests may be placed anywhere.
Find the minimum possible sum of adjacent height differences while satisfying this condition.
Input
The first line contains N, the number of guests, and K, the number of lions. (1 <= N <= 10000, 1 <= K <= N, K <= 1000)
The next K lines contain the heights of the lions, from highest rank to lowest rank. The following N-K lines each contain the height of one other guest.
Every height is an integer from 1 to 2^31 - 1.
Output
Print the minimum possible sum of height differences between adjacent people in a valid procession. The answer does not exceed 2^31 - 1.