Bribe the Prisoners (GCJ2009 Round1C C)

Bribe the Prisoners (GCJ2009 Round1C C)

Problem

一个监狱里有 P 个并排着的牢房。从左至右依次编号为 1,2,⋯,P。最初所有的牢 房里都住着一个囚犯。相邻的两个牢房之间有一个窗户,可以通过它与相邻牢房里的囚犯对话。

现在要释放一些囚犯。如果释放某个牢房里的囚犯,其相邻的牢房里的囚犯就会知道,因而发怒暴动。所以,释放某个牢房里的囚犯同时,必须要贿赂两旁相邻牢房里的囚犯一枚金币。

另外,为了防止释放的消息在相邻牢房间传开,不仅两旁直接相邻的牢房,所有可能听到消息的囚犯,即直到空牢房为止或直到监狱两端为止,此间的所有囚犯都必须给一枚金币。

现在要释放 a_1,a_2,...,a_Q 号牢房里的 Q 名囚犯,释放的顺序还没确定。如果选择所需金币数量尽量少的顺序释放,最少需要多少枚金币?

Input

1
2
P Q
a_1,a_2,...,a_Q

Output

1
ans

Sample

1
2
3
4
5
6
7
8
9
10
Input:
2
8 1
3
20 3
3 6 14

Output:
Case #1: 7
Case #2: 35

Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
int n;
scanf("%d", &n);
for (int c = 1; c <= n; ++c) {
int P, Q;
scanf("%d %d", &P, &Q);
int *a = new int [Q+2];
for (int i = 1; i <= Q; ++i)
scanf("%d ", &a[i]);
a[0] = 0;
a[Q+1] = P + 1;

int **dp = new int*[Q+1];
for (int i = 0; i < Q+1; ++i) {
dp[i] = new int[Q+2];
dp[i][i+1] = 0;
}
// d[i][j] 表示将 A[i+1],...,[j-1] 号囚犯释放所需要的最少金币
for (int w = 2; w <= Q+1; ++w) { // 区间长度
for (int i = 0; i + w <= Q + 1; ++i) { // 左起
int j = i + w, t = INT_MAX;
for (int k = i + 1; k < j; ++k) { // 遍历中间囚犯
t = min(t, dp[i][k] + dp[k][j]); //左右区间值
}
dp[i][j] = t + a[j] - a[i] - 2; // +删除 k 所需要的金币
}
}
printf("Case #%d: %d\n", c, dp[0][Q+1]);
}
return 0;
}

Analysis

  1. 递归枚举。
  2. 释放某个囚犯后,连续的牢房就变成了两段,两段相互独立。
  3. 释放一个区间内囚犯所需要的金币 = 释放其中一个囚犯需要的金币 + 释放左侧所需要的金币 + 释放右侧所需要的金币。
# GCJ

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×