GCJ1C09C - Bribe the *ers

Problem

In a kingdom there are * cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and *ers in adjacent cells are called "neighbours." A wall with a window separates adjacent cells, and neighbours can communicate through that window.

All *ers live in peace until a *er is released. When that happens, the released *er's neighbours find out, and each communicates this to his other neighbour. That *er passes it on to his other neighbour, and so on until they reach a *er with no other neighbour (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A *er who discovers that another *er has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a *er in cell A, all *ers housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.

Assume that each * cell is initially occupied by exactly one *er, and that only one *er can be released per day. Given the list of Q *ers to be released in Q days, find the minimum total number of gold coins needed as bribes if the *ers may be released in any order.

Note that each bribe only has an effect for one day. If a *er who was bribed yesterday hears about another released *er 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 * cells and Q is the number of *ers to be released.
This will be followed by a line with Q distinct cell numbers (of the *ers to be released), space separated, sorted in ascending order.
Output

For each test case, output one line in the format

Case #X: C
where 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
2
8 1
3
20 3
3 6 14

Output 
Case #1: 7
Case #2: 35

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.

解题：这个题目蛮有意思啊。。。本来是进行拆解的，逆向成填充，这样就能像求最优二叉搜索树那样进行动态规划求取了

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 const int INF = 0x3f3f3f3f;

 int dp[maxn][maxn],d[maxn];

 int main(){

     int T,p,q,cs = ;

     scanf("%d",&T);

     while(T--){

         scanf("%d %d",&p,&q);

         for(int i = ; i <= q; ++i)

             scanf("%d",d+i);

         d[] = ;

         d[++q] = p+;

         for(int i = ; i < maxn; ++i) dp[i][i] = ;

         for (int w = ; w <= q; ++w){

             for(int i = ,j = w; j <= q; ++i,++j){

                 dp[i][j] = INF;

                 for(int k = i + ; k < j; ++k)

                     dp[i][j] = min(dp[i][k]+dp[k][j]+d[j]-d[i]-,dp[i][j]);

             }

         }

         printf("Case #%d: %d\n",cs++,dp[][q]);

     }

     return ;

 }