Dynamic programming - linear
Some nails are hammered on a straight plank. Any two nails can be joined by a thread. Connect some pairs of nails with a thread, so that to each nail will be tied with at least one thread, and the total length of all threads will be minimal.
The first line contains the number of nails n (1 ≤ n ≤ 100). The next line contains n numbers - the coordinates of all the nails (non-negative integers not exceeding 10000).
Print the minimum total length of all threads.
5 4 10 0 12 2