当前位置：首页 > news >正文

HDU 3920 Clear All of Them I（DP + 状态压缩 + 贪心）

news 来源：原创 2024/5/6 20:28:58

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3920

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

Sample Input

0 0

6 0

3 0

0 0

1 0

2 1

-1 0

-2 0

Sample Output

Case #1: 6.00

Case #2: 4.41

分析：给每个点编个号，用状态压缩表示射击那些点，射击过的表示为1，dp[i]表示射击状态 i 时最少消耗，答案即为dp[(1<<2*n)-1]

　　先每个点到射击点排个序，每次选最近的一个点，和距离这个点最近的点，这两个就是应该选的点（贪心）

代码如下：

 1 # include<cstdio>
 2 # include<cstring>
 3 # include<algorithm>
 4 # include<iostream>
 5 # include<cmath>
 6 using namespace std;
 7 const int INF = 0xffffff;
 8 double dis[21][21],dp[1<<21];
 9 int vis[1<<21];
10 int n,fx,fy;
11 struct NODE
12 {
13     int x,y;
14 } node[21];
15 double DIS(double x1,double y1,double x2,double y2)
16 {
17     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
18 }
19 bool cmp(NODE a,NODE b)
20 {
21     return DIS(a.x,a.y,fx,fy)<DIS(b.x,b.y,fx,fy);
22 }
23 double DP(int sta)
24 {
25     if(vis[sta])
26         return dp[sta];
27     vis[sta] = 1;
28     if(sta==0)
29         dp[0]=0.0;
30     else
31     {
32         int i;
33         for(i=0; i<2*n; i++)
34         {
35             if((1<<i) & sta)break;
36         }
37         for(int j=i+1; j<2*n; j++)
38         {
39             if((sta & (1<<j))==0)continue;
40             dp[sta]=min(DP(sta^(1<<j)^(1<<i))+dis[i][j],dp[sta]);
41         }
42     }
43     return dp[sta];
44 }
45 int main()
46 {
47     int T,cas=1;
48     int i,j;
49     scanf("%d",&T);
50     for(cas=1; cas<=T; cas++)
51     {
52         scanf("%d%d",&fx,&fy);
53         scanf("%d",&n);
54         for(i=0; i<2*n; i++)
55             scanf("%d%d",&node[i].x,&node[i].y);
56         sort(node,node+2*n,cmp);
57         for(i=0; i<2*n; i++)
58             for(j=i+1; j<2*n; j++)
59             {
60                 dis[i][j]=DIS(node[i].x,node[i].y,fx,fy)+DIS(node[i].x*1.0,node[i].y*1.0,node[j].x*1.0,node[j].y*1.0);
61             }
62         memset(vis,0,sizeof(vis));
63         memset(dp,INF,sizeof(dp));
64         printf("Case #%d: %.2f\n",cas,DP((1<<(2*n))-1));
65     }
66     return 0;
67 }