【洛谷_P1433】吃奶酪

本文主要是介绍【洛谷_P1433】吃奶酪，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

吃奶酪

---

题目描述

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1

4
1 1
1 -1
-1 1
-1 -1

输出 #1

7.41

解题思路

这道题，我们分析数据：1<=n<=15。所以 《 很 显 然 》，这道题是用状压DP，动转移方程如下
：
$$f[i][k]=min(f[i][k],f[j][k-(1<<i-1)]+hh(i,j))$$
然后进行几个特判，赋个初值，就差不多了

#include<iostream>
#include<cstdio>
#include<cmath>
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<<n);j++)f[i][j]=0x3f3f3f3f;for(int k=1;k<(1<<n);k++)for(int i=1;i<=n;i++){if(!(k&(1<<i-1))) continue;if(k==(1<<i-1)){f[i][k]=0;continue; }for(int j=1;j<=n;j++){if(i==j||!(k&(1<<j-1))) continue;f[i][k]=min(f[i][k],f[j][k-(1<<i-1)]+hh(i,j));}}for(int i=1;i<=n;i++)ans=min(ans,f[i][(1<<n)-1]+hh(i,0));printf("%.2lf",ans);
}

这篇关于【洛谷_P1433】吃奶酪的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---