首页 > ACM题库 > HDU-杭电 > HDU 3920-Clear All of Them I-动态规划-[解题报告]HOJ
2015
04-14

HDU 3920-Clear All of Them I-动态规划-[解题报告]HOJ

Clear All of Them I

问题描述 :

Acmers have been the Earth Protector against the evil enemy for a long time, now it’s your turn to protect our home.
  There are 2 * n enemies in the map. Your task is to clear all of them with your super laser gun at the fixed position (x, y).
  For each laser shot, your laser beam can reflect 1 times (must be 1 times), which means it can kill 2 enemies at one time. And the energy this shot costs is the total length of the laser path.
  For example, if you are at (0, 0), and use one laser shot kills the 2 enemies in the order of (3, 4), (6, 0), then the energy this shot costs is 5.0 + 5.0 = 10. 00.
  Since there are 2 * n enemies, you have to shot n times to clear all of them. For each shot, it is you that select two existed enemies and decide the reflect order.
  Now, telling you your position and the 2n enemies’ position, to save the energy, can you tell me how much energy you need at least to clear all of them?
  Note that:
   > Each enemy can only be attacked once.
   > All the positions will be unique.
   > You must attack 2 different enemies in one shot.
   > You can’t change your position.

输入:

The first line contains a single positive integer T( T <= 100 ), indicates the number of test cases.
For each case:
  There are 2 integers x and y in the first line, which means your position.
  The second line is an integer n(1 <= n <= 10), denote there are 2n enemies.
  Then there following 2n lines, each line have 2 integers denote the position of an enemy.
  
  All the position integers are between -1000 and 1000.

输出:

The first line contains a single positive integer T( T <= 100 ), indicates the number of test cases.
For each case:
  There are 2 integers x and y in the first line, which means your position.
  The second line is an integer n(1 <= n <= 10), denote there are 2n enemies.
  Then there following 2n lines, each line have 2 integers denote the position of an enemy.
  
  All the position integers are between -1000 and 1000.

样例输入:

2

0 0
1
6 0
3 0

0 0
2
1 0
2 1
-1 0
-2 0

样例输出:

Case #1: 6.00
Case #2: 4.41

题意:你在一个位置用激光枪灭敌人,给你初始位置,下面是2*n个敌人的位置,你一枪能杀两个,可以杀死任意两个人,激光束的路径是消耗的能量,求最小能量,保证一次只消灭两个敌人,你的位置不变。

这题压缩状态很容易想到,状态也很容易想到,但是会tle,这题的关键在于,贪心和记忆化搜索,记忆化去掉了很多无用的状态,贪心就去掉了一个for,不去这个for还是tle,但是这个贪心不知道怎么证明,每次选最近的一个点,和距离这个点最近的点,这两个就是应该选的点,用笔画了画,发现不了错误,如果这题在比赛中,那一定要去思考贪心。要有这个意识才行。这效率啊,

Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author
4504914 2011-08-27 22:53:28 Accepted 3920 296MS 8472K 1306 B C++ xym2010
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
double dis[21][21],dp[1<<21];
int n,fx,fy,mac;
struct node
{
	int x,y;
}nd[21];
double DIS(double x,double y,double xx,double yy)
{
	return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
bool cmp(node a,node b)
{
	return DIS(a.x,a.y,fx,fy)<DIS(b.x,b.y,fx,fy);
}
double DP(int sta)
{
	if(dp[sta]!=0x7fffffff)
		return dp[sta];
	if(sta==0) {dp[0]=0.0;}
	else
	{
		int tem=sta,i=0;
		for(i=0;i<20;i++)
		{
			if((1<<i)&sta)break;
		}
		for(int j=i+1;j<2*n;j++)
		{
			if((sta&(1<<j))==0)continue;
			dp[sta]=min(DP(sta-(1<<j)-(1<<i))+dis[i][j],dp[sta]);
		}
	}
	//  printf("%d %.2f\n",sta,dp[sta]);
	return dp[sta];
}
int main()
{
	int c,ca=0;
	scanf("%d",&c);
	while(c--)
	{
		ca++;
		scanf("%d%d",&fx,&fy);
		scanf("%d",&n);
		for(int i=0;i<2*n;i++)
		{
			scanf("%d%d",&nd[i].x,&nd[i].y);
		}
		sort(nd,nd+2*n,cmp);
		for(int i=0;i<2*n;i++)
			for(int j=i+1;j<2*n;j++)
			{
				//if(i==j)continue;
				dis[i][j]=DIS(nd[i].x,nd[i].y,fx,fy)+DIS(nd[i].x*1.0,nd[i].y*1.0,nd[j].x*1.0,nd[j].y*1.0);
			}
			printf("Case #%d: ",ca);
			for(int i=0;i<(1<<2*n);i++)
				dp[i]=0x7fffffff;
			printf("%.2f\n",DP((1<<(2*n))-1));
	}
}

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

参考:http://blog.csdn.net/xymscau/article/details/6725580


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  2. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示