Bribe the *ers

题目描述

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 Qdays, 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表示有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 （P是总的*数）and Q is the number of *ers to be released（Q是要释放的罪犯个数）.
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.

Small dataset

1 ≤ P ≤ 100
1 ≤ Q ≤ 5

Large dataset

1 ≤ P ≤ 10000
1 ≤ Q ≤ 100

Sample

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<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

const int maxn = 10010;
int A[maxn];
int dp[maxn][maxn];

int main(void)
{
    int P,Q;
    cin >> P >> Q;
    
    A[0]=0;
    A[Q+1]=P+1;
    
    for(int i=1;i<=Q;i++) cin >> A[i];
    for(int i=0;i<=Q;i++) dp[i][i+1]=0;
    
    for(int len=2;len<=Q+1;len++)
    {
        for(int i=0;i+len<=Q+1;i++)
        {
            int j=i+len,m=0xFFFFFFF;
            for(int k=i+1;k<j;k++)
            {
                m=min(dp[i][k]+dp[k][j],m);
            }
            dp[i][j] = m + (A[j]-A[i]+1)-3;
        }
    }
    cout << dp[0][Q+1] << endl; 
    return 0;
}