吃
奶
酪
吃奶酪
吃奶酪
题目描述
房间里放着
n
n
n 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在
(
0
,
0
)
(0,0)
(0,0)点处。
输入
第一行有一个整数，表示奶酪的数量
n
n
n。
第 22 到第
(
n
+
1
)
(n+1)
(n+1) 行，每行两个实数，第
(
i
+
1
)
(i + 1)
(i+1) 行的实数分别表示第 i 块奶酪的横纵坐
x
i
,
y
i
x_i,y_i
xi,yi
输出
输出一行一个实数，表示要跑的最少距离，保留
2
2
2 位小数。
样例输入
4
1 1
1 -1
-1 1
-1 -1
样例输出
7.41
题目解析
这道题我们可以用状压DP做。对于，每两个点之间的距离，我们可以用欧氏距离来计算
对于两个点
(
x
1
,
y
1
)
(
x
2
,
y
2
)
(x_1,y_1) (x_2,y_2)
(x1,y1)(x2,y2)两点之间的距离公式为
s
q
r
t
(
(
x
1
−
x
2
)
∗
(
x
1
−
x
2
)
+
(
y
1
−
y
2
)
∗
(
y
1
−
y
2
)
)
sqrt ( (x_1-x_2) * (x_1-x_2) + (y_1-y_2) * (y_1-y_2) )
sqrt((x1−x2)∗(x1−x2)+(y1−y2)∗(y1−y2))
code
#include<cmath>#include<stdio.h>#include<iostream> #include<string.h>#include<algorithm>#define db doubleusing namespace std;int n;
db ans=-1,x[20], y[20], f[20][35000];db jl (db x1, db y1, db x2, db y2)
{
return sqrt ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}int main ()
{
scanf ("%d",&n);
memset(f,127,sizeof(f));
for (int i=1; i<=n; ++i) scanf("%lf%lf",&x[i],&y[i]);
for(int s=1;s<=(1<<n)-1;s++)
for(int i=1;i<=n;i++)
{
if((s&(1<<(i-1)))==0) continue;
if(s==(1<<(i-1))) {f[i][s]=0;continue;}
for(int j=1;j<=n;j++)
{
if((s&(1<<(j-1)))==0||i==j) continue;
f[i][s]=min(f[i][s],f[j][s-(1<<(i-1))]+jl(x[i],y[i],x[j],y[j]));
}
}
for(int i=1;i<=n;i++)
{
db s=f[i][(1<<n)-1]+jl(x[i],y[i],x[0],y[0]);
if(ans==-1||ans>s) ans=s;
}
printf("%.2lf\n",ans);
return 0;
}
