网站地图

当前位置: 震情作文网 > 有关画的作文

Bribe the Prisoners

时间:2022-06-21 08:39人气:来源: 未知

题目描述

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 Qdays, 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表示有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 (P是总的监狱数)and Q is the number of prisoners to be released(Q是要释放的罪犯个数).
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: 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
QP
Each cell number is between 1 and P, inclusive.

Small dataset

1 ≤ P ≤ 100
1 ≤ Q ≤ 5

Large dataset

1 ≤ P
1 ≤ Q ≤ 100

Sample


Input

Output

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
#include
#include
#include
using namespace std;

const int maxn=;
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)
            {
                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;
}

文章来源: http://www.everstarry.com文章标题: Bribe the Prisoners

原文地址:http://www.everstarry.com/yghdzw/11138.html

上一篇:2016, v.38;No.270(10)1499-1508

网站首页

下一篇:没有了



本类导航