GoogleCodejam2009 Round 1C Bribe the Prisoners

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: 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 ≤ 10000
1 ≤ Q ≤ 100

Sample


Input
 

Output
 
2
8 1
3
20 3
3 6 14
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.


题目分析:
从直觉上来说,这是一道动态规划的题目,关键是如何建立状态递推。有一个很明显的规律是,释放一个牢房的犯人,只能影响到左边第一个空的牢房和右边第一个空的牢房,而与其它的无关。所以,释放了一个囚犯,整个连续的牢房被分成了2段,而这两段又都可以看成是单独的两个互不影响的一段,这样,脑子里有一种很直觉的想法就是,这是一棵类似于二叉树的结构,这颗二叉树最后的形态就决定了最终的结果。
我们从第二个Case为例子介绍算法:
1.首先对该题所提到的监狱增加两个cell,0号和P + 1号, 这两个cell是不存在的,只是为了增加程序的可编写和公式的一致,我们用一个vector v 来存储释放囚犯的监狱号,v按照从小到达的顺序排列,如第二个例子中,v(0...4) = (0,3, 6, 14, 21)
2. 我们用F[i][j]表示 从v[i]到v[j]这一段中所需要的贿赂金最小值,那么,F[0][4]就是最后需要的结果, 代表从v[0]到v[4]也就是从(0, 21)这之间的牢房中释放囚犯所需要的钱(不包括边界,实际需要钱贿赂的囚犯在1到20号房子中)
3. 例如第三个例子,F[0][4] = Min(F[0][i] + F[i][3]) + (v[4] - v[0] - 2) , 其可以中i = 1, 2, 3
    可以从第三个例子中看到,无论你选择释放哪一个囚犯,所需的金额都是一定的,正好是这段之间住人的牢房数 - 1
4.更加抽象出最终的公式, 我们用L代表左边界, R代表右边界
    F[L][R] = Min(F[L][i] + F[i][R]) + v[R] - V[L] - 2,   i = L + 1, L + 2, ……R- 1,  当L + 1 != R时
    F[L][R] = 0, 当L + 1 == R时, 这个就是上面提到的二叉树的叶子节点
   通过这个公式就可以得到最终的结果了。

 1#include <iostream>
 2#include <vector>
 3#include <queue>
 4#include <string>
 5#include <algorithm>
 6#include <set>
 7#include <map>
 8using namespace std;
 9
10#define ONLINEJUDGE
11#define MAXN 11000
12#define MAXQ 110
13#define MAXP 110
14#define MIN(a, b) ((a) < (b) ? (a):(b))
15
16int P, Q;
17vector<int> v;
18vector<int> Ret, buf;
19int F[MAXP][MAXP];
20
21int Find(int l, int r)
22{
23    if(l + 1 == r)
24    {
25        F[l][r] = 0;
26        return F[l][r];
27    }

28    if(F[l][r] >= 0return F[l][r];
29
30    int i, j;
31    int iMin;
32    iMin = 999999999;
33    for(i = l + 1; i < r; i++)
34    {
35        iMin = MIN(iMin, Find(l, i) + Find(i, r));
36    }

37    F[l][r] = iMin + v[r] - v[l] - 2;
38    return F[l][r];
39}

40
41int main()
42{
43#ifdef ONLINEJUDGE
44    freopen("C-large.in""r", stdin);
45    freopen("C-large.out""w", stdout);
46#endif
47
48    int iCaseTimes, i, j;
49    int iBuf;
50    int iMax, iRet, iMin;
51
52    scanf("%d"&iCaseTimes);
53    for(int k = 0; k < iCaseTimes; k++)
54    {
55        printf("Case #%d: ", k + 1);
56        scanf("%d%d"&P, &Q);
57        v.clear();
58        v.push_back(0);
59        for(i = 0; i < Q; i++)
60        {
61            scanf("%d"&iBuf);
62            v.push_back(iBuf);
63        }

64        v.push_back(P + 1);
65
66        iMin = 0;
67        memset(F, -1sizeof(F));
68        sort(v.begin(), v.end());
69        
70        iMin = 999999999;
71        for(i = 1; i < v.size() - 1; i++)
72        {
73            iMin = MIN(iMin, Find(0, i) + Find(i, v.size() - 1));
74        }

75        F[0][v.size() - 1= iMin + v[v.size() - 1- v[0- 2;
76        printf("%d\n", F[0][v.size() - 1]);
77    }

78    return 0;
79}

posted on 2009-09-14 19:28 Philip85517 阅读(1342) 评论(2)  编辑 收藏 引用 所属分类: GoogleCodeJam

评论

# re: GoogleCodejam2009 Round 1C Bribe the Prisoners[未登录] 2009-09-15 16:09 vincent

googlecodejam啊 ..貌似是9月2日?
当天有事情没参加..orz  回复  更多评论   

# re: GoogleCodejam2009 Round 1C Bribe the Prisoners[未登录] 2009-09-15 23:32 Philip85517

@vincent
9月2号开始的是资格赛,这个是上个星期天的比赛。
估计Round2 是死活进不去了,太弱了……
  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2022年11月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

统计

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜