本文共 825 字，大约阅读时间需要 2 分钟。

吃奶酪

题目描述

房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 (0,0) 点处。

输入格式

第一行有一个整数，表示奶酪的数量 n。

第 2 到第 (n + 1) 行，每行两个实数，第 (i + 1) 行的实数分别表示第 i 块奶酪的横纵坐标 x_i, y_i

输出格式

输出一行一个实数，表示要跑的最少距离，保留 2 位小数。

输入输出样例

输入 #1

41 11 -1-1 1-1 -1

输出 #1

7.41

解题思路

这道题，我们分析数据：1<=n<=15。所以 《 很 显 然 》，这道题是用状压DP，动转移方程如下

#include
   
    #include
    
     #include
     
      using namespace std;int n; double x[20],y[20];double f[30][1<<15],ans=0x3f3f3f3f;double hh(int i,int j){   	return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));}int main(){   	cin>>n;	for(int i=1;i<=n;i++)		scanf("%lf%lf",&x[i],&y[i]);	for(int i=1;i<=n;i++)		for(int j=1;j<(1<