首页 > ACM题库 > HDU-杭电 > HDU 4281-Judges’ response-动态规划-[解题报告]HOJ
2015
05-23

HDU 4281-Judges’ response-动态规划-[解题报告]HOJ

Judges’ response

问题描述 :

  The contest is running and the judges is busy watching the progress of the contest. Suddenly, N – 1 (N <= 16) contestants hand up their hand at the same time. The judges should go to answer the contestants’ question one by one. The judges already foresee that answering contest i’s question would cost Ci minutes. In order to serve all the contestant, each judges is assigned to serve some subset of the contestants. As the judges have limited patience, each one of them can serve the contestants for no more than M minutes.
  You are asked to solve two problems:
  1. At least how many judges should be sent so that they can serve all the contestants? (Because the judges have limited patience, each one of them cannot serve too many contestants.)
  2. If there are infinite number of judges, how to assign the route for each judge so that the sum of their walking time is minimized? Each contestant i is reside in place (xi, yi), the judges are in place (x1, y1). Assuming the walking speed of the judge is 1.

输入:

  There are several test cases, Each case begin with two integer N, M(with the meaning in the above context, 2 <= N <= 16, 0 <= M <= 100000).
  Then N lines follow and line i will contain two numbers x, y(0 <= x, y <= 1000), indicating the coordinate of place i.
  Then another N lines follow and line i will contain numbers Ci(0 <= Ci <= 1000), indicating the time to solve contestant i’s question. C1 will 0 as place 1 is for the judges.
  
  The distance between place i and place j is defined as ceil(sqrt((xi – xj) ^ 2 + (yi – yj) ^ 2)). (ceil means rounding the number up, e.g. ceil(4.1) = 5)

输出:

  There are several test cases, Each case begin with two integer N, M(with the meaning in the above context, 2 <= N <= 16, 0 <= M <= 100000).
  Then N lines follow and line i will contain two numbers x, y(0 <= x, y <= 1000), indicating the coordinate of place i.
  Then another N lines follow and line i will contain numbers Ci(0 <= Ci <= 1000), indicating the time to solve contestant i’s question. C1 will 0 as place 1 is for the judges.
  
  The distance between place i and place j is defined as ceil(sqrt((xi – xj) ^ 2 + (yi – yj) ^ 2)). (ceil means rounding the number up, e.g. ceil(4.1) = 5)

样例输入:

3 3
0 0
0 3
0 1
0
1
2

3 2
0 0
0 3
0 1
0
1
2

3 1
0 0
0 3
0 1
0
1
2
  
16 35
30 40
37 52
49 49
52 64
31 62
52 33
42 41
52 41
57 58
62 42
42 57
27 68
43 67
58 48
58 27
37 69
0
19
30
16
23
11
31
15
28
8
8
7
14
6
19
11

样例输出:

1 6
2 8
-1 -1
8 467

转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents          
by—cxlove 

题目:给出N个人,其中0号是裁判的位置,剩下有N-1的人提问,裁判需要去回答问题,每个人有一个val,每个裁判能拿到的val的上限为K。问题最少需要几个裁判,以及最少时间

http://acm.hdu.edu.cn/showproblem.php?pid=4281 

第一问可以状态压缩DP解决,dp[i]表示状态i需要几个裁判。注~~~贪心 是错的!!!!

第二问就是多个TSP问题,dp[i][j]表示当前位置 在i,可行状态为j的最小费用,best[i]表示对于状态i的最小费用(而且是一个完整状态,裁判都回到原点),因为之前TSP中是求的可行状态,也就是每个裁判的上限不能超过K。之后就是枚举所有状态,对于一个状态,枚举他的所有子集,见代码中的位运算部分。而且两个子集中必须要包含0号结点,因为每个裁判都是从0出发的

可以看这个博客:http://blog.csdn.net/woshi250hua/article/details/7961869

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#define inf 1<<28
#define M 100005
#define N 55
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD 1000000007
using namespace std;
struct Point{
	int x,y;
}p[20];
int n,m,val[20],path[20][20];
int dp[16][1<<16],state[1<<16],tot;
int best[1<<16],ok[1<<16];
int dist(Point p1,Point p2){
	return ceil(sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
}
void Get_dist(){
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) path[i][j]=dist(p[i],p[j]);
}
void Init(){
	for(int i=0;i<n;i++)
		for(int j=0;j<(1<<n);j++)
			dp[i][j]=inf;
	for(int i=0;i<(1<<n);i++)
		best[i]=inf;
	dp[0][1]=0;
}
int check(int state){
	int sum=0;
	for(int i=0;i<n;i++)
		if(state&(1<<i))
			sum+=val[i];
	return sum<=m;
}
bool cmp(int a,int b){return a>b;}
int slove(){
	int dp[1<<16];
	for(int i=0;i<(1<<n);i++) dp[i]=inf;
	dp[0]=0;
	for(int i=0;i<tot;i++){
		for(int j=(1<<n)-1;j>=0;j--){	
			if(dp[j]==inf) continue;
			if(state[i]&j) continue;
			dp[state[i]+j]=min(dp[state[i]+j],dp[j]+1);
		}
	}
	return dp[(1<<n)-1]==inf?-1:dp[(1<<n)-1];
}
int TSP(){
	for(int i=0;i<(1<<n);i++){
		if(ok[i])
			for(int j=0;j<n;j++)
				if(i&(1<<j)){
					best[i]=min(best[i],dp[j][i]+path[j][0]);
					for(int k=0;k<n;k++)
						if(!(i&(1<<k)))
							dp[k][i|(1<<k)]=min(dp[k][i|(1<<k)],dp[j][i]+path[j][k]);
				}
	}
	for(int i=0;i<(1<<n);i++)
		if(i&1)
			for(int j=i&(i-1);j;j=i&(j-1))
				best[i]=min(best[i],best[j]+best[(i-j)|1]);
	return best[(1<<n)-1];
}

int main(){
	while(scanf("%d%d",&n,&m)!=EOF){
		tot=0;
		for(int i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y);
		for(int i=0;i<n;i++) scanf("%d",&val[i]);
		for(int i=0;i<(1<<n);i++) {
			ok[i]=check(i);
			if(ok[i])
				state[tot++]=i;
		}
		Get_dist();
		Init();
		int ans1=slove();
		if(ans1==-1) {printf("-1 -1\n");continue;}
		printf("%d %d\n",ans1,TSP());
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/7966276