GCJ 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             Case #1: 7
8 1           Case #2: 35
3
20 3
3 6 14

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.

这道题想了挺长时间,主要是没顺过那个弯来。其实想明白了就觉得很简单了。关键在于能想到释放了某个囚犯之后,就可以把牢房当做两段独立的牢房来看待,这样问题就变得简单多了,然后再用DP递归来解。
Code :

/*
*题目出处:http://code.google.com/codejam/contest/189252/dashboard#s=p2   Bribe the Prisoners
*解题思路:动态规划
*关键在于要想到,在释放了某个囚犯之后,牢房就可以当成独立的两段来看待
*所以总共所需的金币数=正在释放囚犯A[k]时所需的金币数+释放A[i]~A[k]的囚犯(不包含两端的囚犯)需要的金币数+释放A[k]~A[j]的囚犯(不包含两端的囚犯)需要的金币数
*之后就可以递归计算释放区间A[i]~A[k](不包含两端的囚犯)和A[k]~A[j](不包含两端的囚犯)这两段牢房中的囚犯时所需的最小金币数
*author:Jorbe
*date:  2013.12.8
*/
#include <iostream>
#include <cstdio>

using namespace std;

const int INT_MAX=1e9;
const int MAX_Q=100;
int P,Q,A[MAX_Q+1],dp[MAX_Q+1][MAX_Q+1];  //A[MAX_Q+2]:存储要释放囚犯的牢房号,下标从1开始
										  //dp[MAX_Q+1][MAX_Q+1]:存储结果
void initial()     //初始化dp[]数组
{
	for(int i=0;i<=Q+1;i++)
		for(int j=0;j<=Q+1;j++)
		dp[i][j]=INT_MAX;
}

int get_min(int a,int b)
{
	return a<b?a:b;
}

int solve(int i,int j)  //计算释放牢房号在A[i]~A[j]之间的囚犯所需要的最小金币数
{						//d[i][j]表示释放牢房号在A[i]~A[j]之间的囚犯(不包含两端的囚犯)所需的最小金币数
	if(dp[i][j]!=INT_MAX) return dp[i][j];
	if(i+1>=j) return 0;  //说明A[i]~A[j]之间没有要释放的囚犯
	for(int k=i+1;k<=j-1;k++)
	{
		dp[i][j]=get_min((solve(i,k)+solve(k,j)+A[j]-A[i]-2),dp[i][j]);
	}
	return dp[i][j];
}

int main()
{
	int N;
	cin>>N;
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d",&P,&Q);
		initial();     //初始化dp数组
		A[0]=0;        //牢房两端即墙壁赋值给A[0]和A[Q+1]
		A[Q+1]=P+1;
		for(int j=1;j<=Q;j++)   //输入A[]
		{
			scanf("%d",&A[j]);
		}
		printf("Case #%d: %d\n",i,solve(0,Q+1));
	}
	return 0;
}

如果不用递归的话,可以这样来解:(评注:虽然递归算法效率不高,但如果条件允许的话还是用递归来解比较好,因为递归算法简单明了,代码可读性也好。下面的代码如果不能理解进去的话会很难读懂。)

/*
*算法来自《挑战程序设计竞赛》一书,P131页
*/
void solve()
{
	//为了处理方便,将两端加入A中
	A[0]=0;
	A[Q+1]=P+1;
    //初始化
	for(int q=0;q<=Q;q++){
		dp[q][q+1]=0;
	}

	//从短的区间开始填充dp
	for(int w=2;w<=Q+1;w++){
		for(int i=0;i+w<=Q+1;i++){
			//计算dp[i][j]
			int j=i+w,t=INT_MAX;
			//枚举最初释放的囚犯,计算最小的费用
			for(int k=i+1;k<j;k++){
				t=min(t,dp[i][k]+dp[k][j]);
			}

			//最初的释放还需要与所释放囚犯无关的A[j]-A[i]-2枚金币
			dp[i][j]=t+A[j]-A[i]-2;
		}
	}

	printf("%d\n",dp[0][Q+1]);
}

Tagged on: , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>