GCJ1C09C  Bribe the Prisoners
Problem
In a kingdom there are prison cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and prisoners in adjacent cells are called "neighbours." A wall with a window separates adjacent cells, and neighbours can communicate through that window.
All prisoners live in peace until a prisoner is released. When that happens, the released prisoner's neighbours find out, and each communicates this to his other neighbour. That prisoner passes it on to his other neighbour, and so on until they reach a prisoner with no other neighbour (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell A, all prisoners housed on either side of cell A  until cell 1, cell P or an empty cell  need to be bribed.
Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of Q prisoners to be released in Q days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.
Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.
Input
The first line of input gives the number of cases, N. N test cases follow. Each case consists of 2 lines. The first line is formatted as
P Q
where P is the number of prison cells and Q is the number of prisoners to be released.This will be followed by a line with Q distinct cell numbers (of the prisoners to be released), space separated, sorted in ascending order.
Output
For each test case, output one line in the format
Case #X: Cwhere X is the case number, starting from 1, and C is the minimum number of gold coins needed as bribes.
Limits
1 ≤ N ≤ 100
Q ≤ P
Each cell number is between 1 and P, inclusive.
Large dataset
1 ≤ P ≤ 10000
1 ≤ Q ≤ 100
Sample
Input 
Output 
2 
Case #1: 7 
Note
In the second sample case, you first release the person in cell 14, then cell 6, then cell 3. The number of gold coins needed is 19 + 12 + 4 = 35. If you instead release the person in cell 6 first, the cost will be 19 + 4 + 13 = 36.
hide comments
Sigma Kappa:
20170918 19:28:42
I wish current GCJ's 1st round problems were like this... BTW this is a carbon copy of http://www.spoj.com/problems/BRKSTRNG/ 

kshubham02:
20160604 13:27:06
Be careful about the output format. I was displaying just the numbers and it costed me two WA. 

SUBHAM SANGHAI:
20160525 08:05:26
Nice dp .. my 100 th :D 

maverick_10:
20160203 14:34:44
A very good dp problems.


naruto09:
20160123 07:20:06
beautiful question....:) :D 

@DubeY@:
20150806 20:33:22
please provide any spacial case......getting back to back WA !! 

kelaseek:
20150108 05:32:55
you should memoize 

Tapashee Tabassum Urmi:
20141229 17:58:31
Awesome solution for large dataset. :) 

a1160576:
20140718 12:35:13
I was equal fastest with least memory amongst solutions that speed, can't complain.


Apoorv Jindal:
20131107 23:05:36
wouldn't a greedy solution work? does it have to be dp? @shafaet could you give me a test case where my submission is wrong.submission id 10440600 thanks 
Added by:  Shafaet 
Date:  20130507 
Time limit:  20s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Google Codejam 2009, Round 1C, Problem C 