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个敌人，消灭敌人的顺序不能导致消耗的能量不同，很容易想到用状态dp压缩，由于2*n<=20,而2^(20)*(2n)*(2n)达到了上亿的复杂度，所以经过分析和提交果断超时了
继续分析可以发现对于消灭敌人a,b如果(x,y)->a < (x,y)->b的路径则肯定是先消灭a再消灭b,所以对于消灭敌人a,则下一个消灭的敌人一定是路径长度大于发射点到a的点
对敌人到达发射点的距离进行从小到大排序，如果消灭敌人j,则下一个消灭的敌人从j+1开始
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std;
const int MAX=(1<<20)+10;
int n,sx,sy,num;
double dp[MAX];
bool mark[MAX];
struct Node{
int x,y;
double dist;
bool operator<(const Node &a)const{
return dist<a.dist;
}
}s[22];
double cal(int x1,int y1,int x2,int y2){
double sum=(x1-x2)*(x1-x2)*1.0+(y1-y2)*(y1-y2)*1.0;
return sqrt(sum);
}
/*double dfs(int i){
if(mark[i])return dp[i];
mark[i]=true;
int j=0;
while(i&(1<<j) && j<n)++j;
for(int k=j+1;k<n;++k){
if(i&(1<<k))continue;
dp[i]=min(dp[i],s[j].dist+cal(s[j].x,s[j].y,s[k].x,s[k].y)+dfs(i|(1<<j)|(1<<k)));
}
return dp[i];
}*/
void DP(){
int bit=1<<n;
for(int i=1;i<bit;++i)dp[i]=INF*1.0;
for(int i=0;i<bit;++i){
if(dp[i] == INF*1.0)continue;
int j=0;
while(i&(1<<j) && j<n)++j;
for(int k=j+1;k<n;++k){
if(i&(1<<k))continue;
int t=i|(1<<j)|(1<<k);
dp[t]=min(dp[t],dp[i]+s[j].dist+cal(s[j].x,s[j].y,s[k].x,s[k].y));
}
}
printf("Case #%d: %.2lf\n",++num,dp[bit-1]);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&sx,&sy);
scanf("%d",&n);
n=2*n;
for(int i=0;i<n;++i)scanf("%d%d",&s[i].x,&s[i].y),s[i].dist=cal(sx,sy,s[i].x,s[i].y);
sort(s,s+n);
DP();
//int bit=1<<n;
//for(int i=0;i<bit;++i)dp[i]=INF*1.0;
//dp[bit-1]=0;
//memset(mark,false,sizeof mark);
//printf("Case #%d: %.2lf\n",++num,dfs(0));
}
return 0;
}
hdu 3920之状态压缩dp,布布扣,bubuko.com
原文：http://blog.csdn.net/xingyeyongheng/article/details/22821377