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
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
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.
題目分析：
從直覺(jué)上來(lái)說(shuō)，這是一道動(dòng)態(tài)規(guī)劃的題目，關(guān)鍵是如何建立狀態(tài)遞推。有一個(gè)很明顯的規(guī)律是，釋放一個(gè)牢房的犯人，只能影響到左邊第一個(gè)空的牢房和右邊第一個(gè)空的牢房，而與其它的無(wú)關(guān)。所以，釋放了一個(gè)囚犯，整個(gè)連續(xù)的牢房被分成了2段，而這兩段又都可以看成是單獨(dú)的兩個(gè)互不影響的一段，這樣，腦子里有一種很直覺(jué)的想法就是，這是一棵類似于二叉樹(shù)的結(jié)構(gòu)，這顆二叉樹(shù)最后的形態(tài)就決定了最終的結(jié)果。
我們從第二個(gè)Case為例子介紹算法：
1.首先對(duì)該題所提到的監(jiān)獄增加兩個(gè)cell，0號(hào)和P + 1號(hào)， 這兩個(gè)cell是不存在的，只是為了增加程序的可編寫和公式的一致，我們用一個(gè)vector v 來(lái)存儲(chǔ)釋放囚犯的監(jiān)獄號(hào)，v按照從小到達(dá)的順序排列，如第二個(gè)例子中，v(0...4) = (0,3, 6, 14, 21)
2. 我們用F[i][j]表示 從v[i]到v[j]這一段中所需要的賄賂金最小值，那么，F(xiàn)[0][4]就是最后需要的結(jié)果， 代表從v[0]到v[4]也就是從(0, 21)這之間的牢房中釋放囚犯所需要的錢（不包括邊界,實(shí)際需要錢賄賂的囚犯在1到20號(hào)房子中）
3. 例如第三個(gè)例子，F(xiàn)[0][4] = Min(F[0][i] + F[i][3]) + (v[4] - v[0] - 2) , 其可以中i = 1， 2， 3
可以從第三個(gè)例子中看到，無(wú)論你選擇釋放哪一個(gè)囚犯，所需的金額都是一定的，正好是這段之間住人的牢房數(shù) - 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, 當(dāng)L + 1 != R時(shí)
F[L][R] = 0, 當(dāng)L + 1 == R時(shí)， 這個(gè)就是上面提到的二叉樹(shù)的葉子節(jié)點(diǎn)
通過(guò)這個(gè)公式就可以得到最終的結(jié)果了。
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] >= 0) return 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, -1, sizeof(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}